#include <bits/stdc++.h>
using namespace std;
struct Node{
    int id,w;
};
int n, m, f1[100005],g[100005],a[100005];
bool vis[100005];
vector<int>v[100005];
vector<int>v1[100005];
bool operator<(const Node &x,const Node &y){
	return x.w>y.w;
}

void dijkstra(){
	memset(f1,0x3f,sizeof(f1));
	memset(vis,0,sizeof(vis));
	f1[1] = a[1];
	priority_queue<Node>q;
	q.push({1,a[1]});
	while (!q.empty())
	{
		int x=q.top().id;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for (int y:v[x]){
			if (f1[y]>min(f1[x],a[y])){
				f1[y]=min(f1[x],a[y]);
				q.push({y,f1[y]});
			}
		}
	}
}
void dijkstra2()
{
	memset(g,-0x3f,sizeof g);
	memset(vis, 0, sizeof(vis));
	g[n] = a[n];
	priority_queue<Node>q;
	q.push({n,a[n]});
	while(!q.empty())
	{
		int x=q.top().id;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int y:v1[x]){
			if(g[y]<max(g[x],a[y])){
				g[y]=max(g[x],a[y]);
				q.push({y,g[y]});
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int aa,bb,cc;
		cin>>aa>>bb>>cc;
		if(cc){
			v[aa].push_back(bb);
			v1[bb].push_back(aa);
		}
		else{
			v[aa].push_back(bb);
			v[bb].push_back(aa);
			v1[aa].push_back(bb);
			v1[bb].push_back(aa);
		}
	}
	dijkstra();
	dijkstra2();
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,g[i]-f1[i]);
	}
	cout<<ans;
	return 0;
}

对必关