#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n,m,tot=0,tot2=0,price[N];
int ver[N],head[N],Next[N],d[N],v[N];
int ver2[N],head2[N],Next2[N],d2[N],v2[N];

queue<int> q; 

void add(int x,int y){
	ver[tot]=y;//真实数据                                         
	Next[tot]=head[x];head[x]=tot++;//head和next数组保存的是ver数组的下标 
}
void add2(int x,int y){
	ver2[tot2]=y;//真实数据                                         
	Next2[tot2]=head2[x];head2[x]=tot2++;//head和next数组保存的是ver数组的下标 
}

void spfa(int st){
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v)); 
	d[st]=price[st];v[st]=1;
	q.push(st);
	while(q.size()){
		int x=q.front();q.pop();
		v[x]=0;
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i];
			if(d[y]>min(d[x],price[y])){
				d[y]=min(d[x],price[y]);
				if(!v[x]) v[y]=1,q.push(y); 
			}
		}
	}
} 
void spfa2(int st){
	memset(d2,0,sizeof(d2));
	memset(v2,0,sizeof(v2)); 
	d2[st]=price[st];v2[st]=1;
	q.push(st);
	while(q.size()){
		int x=q.front();q.pop();
		v2[x]=0;
		for(int i=head2[x];i;i=Next2[i]){
			int y=ver2[i];
			if(d2[y]<max(d2[x],price[y])){
				d2[y]=max(d2[x],price[y]);
				if(!v2[x]) v2[y]=1,q.push(y); 
			}
		}
	}
} 

int main(){
	freopen("trade.in","r",stdin);
	freopen("trade.out","w",stdout);

	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&price[i]);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(z==1){
		
			add(x,y);add2(y,x);
		}
		if(z==2){
			add(x,y);add(y,x);add2(y,x);add2(x,y);
		} 
	}
//	for(int i=1;i<m;i++) cout<<head[i]<<" "<<ver[i]<<" "<<Next[i]<<endl; 
//	for(int i=1;i<m;i++) cout<<head2[i]<<" "<<ver2[i]<<" "<<Next2[i]<<endl;
	spfa(1);
	spfa2(n);
	int ans=0;
	for(int i=1;i<=n;i++){
//	cout<<d2[i]<<" "<<d[i]<<endl;
		ans=max(ans,d2[i]-d[i]);
	}
	cout<<ans<<endl;
	return 0;
}