#include<bits/stdc++.h>
using namespace std;

const int N=1e7+10;
int n,m,w[N],x,y,z,tota,totb,ans;
int heada[N],vera[N],nxta[N];
int headb[N],verb[N],nxtb[N];
int disa[N],disb[N];
bool visa[N],visb[N];

void adda(int u,int v){
	vera[++tota]=v;
	nxta[tota]=heada[u];
	heada[u]=tota;
}

void addb(int u,int v){
	verb[++totb]=v;
	nxtb[totb]=headb[u];
	headb[u]=totb;
}

void dijkstraa(){
	memset(disa,0x3f,sizeof(disa));
	priority_queue<pair<int,int> > q;
	disa[1]=w[1];
	q.push(make_pair(-disa[1],1));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(visa[u]){
			continue;
		}
		visa[u]=true;
		for(int i=heada[u];i;i=nxta[i]){
			int v=vera[i];
			if(disa[v]>min(disa[u],w[v])){
				disa[v]=min(disa[u],w[i]);
				q.push(make_pair(-disa[v],v));
			}
		}
	}
	return ;
}

void dijkstrab(){
	memset(disb,~0x3f,sizeof(disb));
	priority_queue<pair<int,int> > q;
	disb[n]=w[n];
	q.push(make_pair(disb[n],n));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(visb[u]){
			continue;
		}
		visb[u]=true;
		for(int i=headb[u];i;i=nxtb[i]){
			int v=verb[i];
			if(disb[v]<max(disb[u],w[v])){
				disb[v]=max(disb[u],w[i]);
				q.push(make_pair(disb[v],v));
			}
		}
	}
	return ;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		if(z==1){
			adda(x,y);
			addb(y,x);
		}else{
			adda(x,y);
			adda(y,x);
			addb(x,y);
			addb(y,x);
		}
	}
	dijkstraa();
	dijkstrab();
	for(int i=1;i<=n;i++){
		ans=max(ans,disb[i]-disa[i]);
	}
	cout<<ans;
	return 0;
}