#include<bits/stdc++.h>
using namespace std;
const int maxn=114514;
vector< int > edge[maxn],fanedge[maxn];
queue< int > q,qq;
int a[maxn],dist[maxn],ddist[maxn],visit[maxn],visit1[maxn],n,m;
int main(){
	memset(visit,0,sizeof(visit));
	memset(visit1,0,sizeof(visit1));
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		edge[x].push_back(y);
		fanedge[y].push_back(x); 
		if(z==2){
		    edge[y].push_back(x);	
		    fanedge[x].push_back(y); 
		}
	}
	visit[1]=1;
	q.push(1);
	dist[1]=a[1];
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<edge[u].size();i++){
			int v=edge[u][i];
			if(visit[v]==1)continue;
			visit[v]=1;
			dist[v]=min(dist[u],a[v]);
			q.push(v);
		}
	}
//	for(int i=1;i<=n;i++){
//		cout<<dist[i]<<" ";
//	}//cout<<endl<<endl;
	ddist[n]=a[n];
	qq.push(n);
	visit1[n]=1;
	while(!qq.empty()){
		int u=qq.front();qq.pop();
		for(int i=0;i<fanedge[u].size();i++){
			int v=fanedge[u][i];
			if(visit1[v]==1)continue;
			visit1[v]=1;
			ddist[v]=max(ddist[u],a[v]);
			qq.push(v);
		}
    }
//	for(int i=1;i<=n;i++)cout<<ddist[i]<<" ";
	cout<<endl<<endl;
	int ans=0;
	for(int i=1;i<=n;i++){
	    ans=max(ans,ddist[i]-dist[i]);	
	}
	cout<<ans<<endl;
	return 0;
}