#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>
#define X 1000005
#define N 100006
using namespace std;
int head[X],ver[X],Next[X],edge[N],edge_c[N],tot,num;
int stack[X],low[X],dfn[X],top,scc,ans=0;
bool ind[X],b1[N],b2[N];
vector<int> v[N];
int nh[X],nv[X],nn[X],pep,vt[N],edge_u[N];
int fnh[X],fnv[X],fnn[X],fpep;
int n,m,rud1[N],rud2[N];
void add(int x,int y) {
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void add_c(int x,int y) {
	nv[++pep]=y,nn[pep]=nh[x],nh[x]=pep;
}
void add_u(int x,int y) {
	fnv[++fpep]=y,fnn[fpep]=fnh[x],fnh[x]=fpep;
}
void tarjan(int x) {
	low[x]=dfn[x]=++num;
	stack[++top]=x;
	ind[x]=1;
	for(int i=head[x]; i; i=Next[i])
		if(!dfn[ver[i]]) {
			tarjan(ver[i]);
			low[x]=min(low[x],low[ver[i]]);
		} else if(ind[ver[i]]) {
			low[x]=min(low[x],dfn[ver[i]]);
		}
	if(low[x]==dfn[x]) {
		int y;
		scc++;
		do {
			y=stack[top--];
			v[scc].push_back(y);
			ind[y]=0;
			vt[y]=scc;
		} while(y!=x);
	}
}
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++)cin>>edge[i];
	for(int i=1; i<=m; i++) {
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y);
		if(z==2)add(y,x);
	}
	memset(edge_c,0x3f,sizeof(edge_c));
	tarjan(1);
	int f1,f2;
	for(int i=1; i<=scc; i++) {
		for(int j=0; j<v[i].size(); j++) {
			if(v[i][j]==1)f1=i;
			if(v[i][j]==n)f2=i;
			edge_c[i]=min(edge_c[i],edge[v[i][j]]);
			edge_u[i]=max(edge_u[i],edge[v[i][j]]);
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=head[i]; j; j=Next[j]) {
			if(vt[i]!=vt[ver[j]]) {
				add_c(vt[i],vt[ver[j]]);
				rud1[vt[ver[j]]]++;
				add_u(vt[ver[j]],vt[i]);
				rud2[vt[i]++];
			}
		}
	}
	queue<int> q1,q2;
	q1.push(f1);
	q2.push(f2);
	b1[f1]=1;
	b2[f2]=1;
	int uux;
	q1.push(f1);
	q2.push(f2);
	while(!q1.empty()) {
		uux=q1.front();
		q1.pop();
		for(int i=nh[uux]; i; i=nn[i]) {
			int y=nv[i];
			edge_c[y]=min(edge_c[uux],edge_c[y]);
			rud1[y]--;
			if(rud1[y]==0)q1.push(y);
		}
	}
	while(!q2.empty()) {
		uux=q2.front();
		q2.pop();
		for(int i=fnh[uux]; i; i=fnn[i]) {
			int y=fnv[i];
			edge_u[y]=max(edge_u[uux],edge_u[y]);
			rud2[y]--;
			if(rud2[y]==0)q2.push(y);
		}
	}
	for(int i=1; i<=scc; i++)
		ans=max(ans,edge_u[i]-edge_c[i]);
	cout<<ans;
	return 0;
}

用的tarjan+拓扑，hack全过，官方只对#1#2