#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],n,m;
int main(){
	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); 
		}
	}
	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];
			dist[v]=min(dist[u],a[v]);
			q.push(v);
		}
	}
	ddist[n]=a[n];
	qq.push(n);
	while(!qq.empty()){
		int u=q.front();qq.pop();
		for(int i=0;i<fanedge[u].size();i++){
			int v=fanedge[u][i];
			ddist[v]=max(ddist[u],a[v]);
			qq.push(v);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans=max(ans,ddist[i]-dist[i]);
	cout<<ans<<endl;
	return 0;
}