#include <bits/stdc++.h>
using namespace std;
const int MN=1e5+10;
const int MM=5e5+10;

int n,m;
int pr[MN],dis[MN],dis2[MN],vis[MN];
vector<int> edge[MN];
vector<int> redge[MM];
queue<int> q;

void spfa() {
	q.push(1);
	dis[1] = pr[1];
	vis[1] = 1;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int v : edge[u]) {
			if(dis[v]>min(dis[u],pr[v])) {
				dis[v]=min(dis[u],pr[v]);
				if(!vis[v]) {
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
void spfa2() {
	q.push(n);
	dis[n] = pr[n];
	vis[n] = 1;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int v : redge[u]) {
			if(dis2[v]<max(dis2[u],pr[v])) {
				dis2[v]=max(dis2[u],pr[v]);
				if(!vis[v]) {
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
int main() {
	cin>>n>>m;
	for(int i = 1; i <= n; i++) {
		cin>>pr[i];
	}
	for(int i = 1; i <= m; i++) {
		int x,y,z;
		cin>>x>>y>>z;
		if(z==1) {
			edge[x].push_back(y);
			redge[y].push_back(x);
		} else {
			edge[x].push_back(y);
			edge[y].push_back(x);
			redge[y].push_back(x);
			redge[x].push_back(y);
		}
	}
	memset(dis,0x3f,sizeof(dis));
	memset(dis2,0,sizeof(dis2));
	spfa();
	memset(vis,0,sizeof(vis));
	spfa2();
	int ans= 0;
	for(int i = 1; i <= n; i ++) {
		ans = max(ans,dis2[i]-dis[i]);
	}
	cout<<ans<<endl;

	return 0;
}