#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z,id=0;
int v[5000005],a[1000005],p[1000005];
int head[1000005],ans[1000005];
struct tr{
	int nx;
	int y,x;
}N[1000005];
void ja(int x,int y){
	id++;
	N[id].x=x;
	N[id].y=y;
	N[id].nx=head[x];
	head[x]=id;
}
void bfs(){
	queue<int> q;
	q.push(1);
	while(q.size()!=0){
		int x=q.front();
		q.pop();
		for(int t=head[x];t>0;t=N[t].nx){
			if(v[N[t].y]<a[N[t].x]) {
				a[N[t].y]=v[N[t].y];
			}else a[N[t].y]=a[N[t].x];
			ans[N[t].y]=v[N[t].y]-a[N[t].y];
			if(ans[N[t].x]>ans[N[t].y]) ans[N[t].y]=ans[N[t].x];
		    if(p[t]==0){
		    	q.push(t);
		    	p[t]=1;
			}
		    
		}
	}
}
int main(){
	//freopen("trade.in","r",stdin);
	//freopen("trade.out","w",stdout);
	cin>>n>>m;
	for(int t=1;t<=100005;t++){
		a[t]=1000;
	}
	for(int t=1;t<=n;t++){
		cin>>v[t];
	}
	for(int t=1;t<=m;t++){
		cin>>x>>y>>z;
		ja(x,y);
		if(z==2){
			ja(y,x);
		}
	}
	bfs();
	cout<<ans[n];
	return 0;
}