码风一般，代码更臭
大佬们见谅qwq

#include <bits/stdc++.h>
using namespace std;
const int MAX=100005; 
int n,m,v[MAX],mx[MAX],mi[MAX],used[MAX];
struct edgem{
	int next,to;
}e[MAX*27];
int head[MAX],tot;

inline void add(int ax,int ay)
{
	e[++tot].next=head[ax];
	e[tot].to=ay;
	head[ax]=tot;
}

int low[MAX],dfn[MAX],cnt;
int zhan[MAX],is[MAX],tp;
int cg,g[MAX];
inline void tarjan(int xu)
{
	low[xu]=dfn[xu]=++cnt;
	zhan[++tp]=xu;
	is[xu]=used[xu]=1;
	for(int i=head[xu];i;i=e[i].next)
	{
		int nxt=e[i].to;
		if(is[nxt]){
			low[xu]=min(dfn[nxt],low[xu]);
			continue;
		}
		if(!dfn[nxt])
		{
			tarjan(nxt);
			low[xu]=min(low[nxt],low[xu]);
		}
	}
	if(low[xu]==dfn[xu])
	{
		++cg;
		int mmax=-1,mmin=500*MAX;
		while(zhan[tp+1]!=xu)
		{
			int now=zhan[tp];
			g[now]=cg;
			is[now]=0;
			mmax=max(mmax,v[now]);
			mmin=min(mmin,v[now]);
			--tp;
		}
		mx[cg]=mmax;
		mi[cg]=mmin;
	}
}

int minal[MAX],ans[MAX];
inline void search(int xu)
{
	minal[xu]=min(minal[xu],mi[xu]);
	ans[xu]=max(ans[xu],mx[xu]-minal[xu]);
	for(int i=head[xu];i;i=e[i].next)
	{
		int nxt=e[i].to;
		minal[nxt]=min(minal[xu],mi[nxt]);
		search(nxt);
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i) scanf("%d",&v[i]);
	for(int i=1;i<=m;++i)
	{
		int ax,ay,az;
		scanf("%d%d%d",&ax,&ay,&az);
		if(az==1){
			add(ax,ay);
		}else{
			add(ax,ay);
			add(ay,ax);
		}
	}
	for(int i=1;i<=n;++i) 
	{
		if(!used[i]) tarjan(i); 
	}
	memset(minal,63,sizeof(minal));
	for(int i=1;i<=n;++i)
	{
		for(int j=head[i];j;j=e[j].next)
		{
			int nxt=e[j].to;
			if(g[nxt]!=g[i]) add(n+g[i],n+g[nxt]);
		}
	}
	for(int i=1;i<=cg;++i){
		mi[n+i]=mi[i];
		mx[n+i]=mx[i];
	}
	search(n+g[1]);
	cout<<ans[n+g[n]]<<endl;
	return 0;
}
/*
5 5 
4 3 5 6 1 
1 2 1 
1 4 2
2 3 2 
3 5 1 
4 5 2 
*/