#include<bits/stdc++.h>
#define N 100001
using namespace std;
int cost[N],d[N],fa[N],vis[N],mx[N>>2],nmx[N>>2],mn[N>>2],xb,s,n,m,x,y,z,t,k,cnt,of[N],ss;
stack<int> st;
vector<int> e[N];
set<int> ne[N];
queue<int> q;
inline void dfs(int x){
    if(!vis[x])
        st.push(x);
	d[x]=fa[x]=++s;
	vis[x]=1;
	for(int i=0;i<e[x].size();++i){
		int y=e[x][i];
		if(!d[y]){
			dfs(y);
			fa[x]=min(fa[x],fa[y]);
		}else
		if(vis[y])
			fa[x]=min(fa[x],d[y]);
	}
	if(fa[x]==d[x]){
		of[0]++;
		while(st.top()!=x){
			vis[st.top()]=0,of[st.top()]=of[0];
			st.pop();
		}
		vis[x]=0,of[x]=of[0];
		st.pop();
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		cin>>cost[i];
	for(int i=1;i<=m;++i){
		cin>>x>>y>>z;
		e[x].push_back(y);
		if(z==2)
			e[y].push_back(x);
	}
	for(int i=1;i<=n;++i)
		if(!d[i])
			dfs(i);
	for(int i=1;i<=n;++i){
		for(int j=0;j<e[i].size();++j){
			if(of[i]!=of[e[i][j]])
				ne[of[i]].insert(of[e[i][j]]);
		}
	}
    memset(mn,1,sizeof(mn));
	for(int i=1;i<=n;++i){
		nmx[of[i]]=max(nmx[of[i]],cost[i]);
		mn[of[i]]=min(mn[of[i]],cost[i]);
	}
	for(int i=1;i<=of[0];++i)
		mx[i]=nmx[i]-mn[i];
	
	q.push(of[1]); 
	while(!q.empty()){
		k=q.front();
		q.pop();
		for(set<int>::iterator it=ne[k].begin();it!=ne[k].end();it++){
            mn[*it]=min(mn[*it],mn[k]);
			mx[*it]=max(max(mx[k],mx[*it]),nmx[*it]-mn[*it]);
			q.push(*it);
        }
		/*for(int i=0;i<ne[k].size();++i){
			mn[ne[k][i]]=min(mn[ne[k][i]],mn[k]);
			mx[ne[k][i]]=max(max(mx[k],mx[ne[k][i]]),nmx[ne[k][i]]-mn[ne[k][i]]);
			q.push(ne[k][i]);
		}*/
	}	
	cout<<mx[of[n]];
	return 0;
}

MLE #4,5,6