用的tarjan缩点+topsort，

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
//#include<ctime>
//#include<cstdlib>
#define ll long long
#define INF_INT 0x3f3f3f3f
char Ch;
int ff;
inline void rd(int &x){
	x=0,ff=1,Ch=getchar();
	while((Ch<'0'||Ch>'9')&&Ch!='-')Ch=getchar();
	if(Ch=='-')Ch=getchar(),ff=-1;
	while(Ch>='0'&&Ch<='9'){
		x=(x<<1)+(x<<3)+Ch-'0';
		Ch=getchar();
	}
	x*=ff;
}
inline int random(int x){
	return (long long)rand()*rand()%x;
}
using namespace std;
const int N=1e5+5,M=5e5+5;
int n,m,cnt,Top,sign,scc,ans;
int a[N],du[N];
int dfn[N],low[N],st[N],bl[N],mx[N],mn[N];
bool vis[N];
vector<int>v[N];
int to[M<<1],nxt[M<<1];
int h[N];
int d[N],f[N];
inline void add(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=h[x];
	h[x]=cnt;
}
void tarjan(int x){
	dfn[x]=low[x]=++sign;
	vis[x]=1;
	st[++Top]=x;
	for(auto y:v[x]){
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(vis[x]) {
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x]) {
		scc++;
		int y,p=-INF_INT,q=INF_INT;
		do{
			y=st[Top--];
			vis[y]=0;
			bl[y]=scc;
			p=max(p,a[y]);
			q=min(q,a[y]);
		}while(y!=x);
		mx[scc]=p,mn[scc]=q;
	}
}
void topsort(){
//	memset(d,0x3f,sizeof(d));
	queue<int>q;
	q.push(bl[1]);
	d[bl[1]]=mn[bl[1]];
	for(int x,y;!q.empty();){
		x=q.front(),q.pop();
		for(int i=h[x];i;i=nxt[i]){
			y=to[i];
			d[y]=min(d[x],mn[y]);
			f[y]=max(max(f[x],0),mx[y]-d[y]);
			if((--du[y])==0)q.push(y);
		}
	}
}
int main(){
//	srand(time(0));
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	memset(mn,0x3f,sizeof(mn));
//	memset(mx,-0x3f,sizeof(mx));
	rd(n),rd(m);
	for(int i=1;i<=n;i++)rd(a[i]);
	for(int i=1,x,y,op;i<=m;i++){
		rd(x),rd(y),rd(op);
		v[x].emplace_back(y);
		if(op==2)v[y].emplace_back(x);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	for(int i=1;i<=n;i++)
		for(auto j:v[i])
			if(bl[i]^bl[j])
				add(bl[i],bl[j]),du[bl[j]]++;
	topsort();
//	for(int i=1;i<=scc;i++)
//		cout<<f[i]<<" ";
//	cout<<endl;
	printf("%d",f[bl[n]]);
	return 0;
}