#include<bits/stdc++.h>
#define COGS
using namespace std;
const int maxn=100010;
struct edge{
	int from,to,cost;
	edge(int u,int v,int d):from(u),to(v),cost(d){}
	bool operator <(const edge&rhs)const{
		return cost<rhs.cost;
	}
};
vector<edge> E;
vector<edge> Rev;
vector<int> G[maxn];
vector<int> GR[maxn];
inline void add_edge(int from,int to,int type){
	G[from].push_back(to);
	GR[to].push_back(from);
	if (type==2){
		G[to].push_back(from);
		GR[from].push_back(to);
	}
}
int n,m,temp1,temp2,temp3;
int price[maxn],sp[maxn],lp[maxn];
inline void in(){
	#ifdef COGS
	freopen("trade.in","r",stdin);
	freopen("trade.out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d",&price[i]);
		lp[i]=-1,sp[i]=10000000;
	}
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&temp1,&temp2,&temp3);
		add_edge(temp1,temp2,temp3);
	}
}
inline void SPFA(){
	queue<int> que;
	que.push(1);
	sp[1]=price[1];
	while(!que.empty()){
		int u=que.front();que.pop();
		int num=G[u].size();
		for (int i=0;i<num;i++){
			int t=G[u][i];
			if (sp[u]<sp[t]){
				sp[t]=sp[u];que.push(t);
				if (price[t]<sp[t]){
					sp[t]=price[t];
				}
			}
		}
	}
}
inline void spfa(){
	queue<int> que;
	que.push(n);
	lp[n]=price[n];
	while(!que.empty()){
		int u=que.front();que.pop();
		int num=GR[u].size();
		for (int i=0;i<num;i++){
			int t=GR[u][i];
			if (lp[u]>lp[t]){
				lp[t]=lp[u];que.push(t);
				if (price[t]>lp[t]){
					lp[t]=price[t];
				}
			}
		}
	}
}
inline void deal(){
	SPFA();
	spfa();
}
inline void p(){
	int ans=-1;
	for (int i=1;i<=n;i++){
		ans=max(ans,lp[i]-sp[i]);
	}
	printf("%d",ans);
}
int Main(){
	//freopen("a.txt","r",stdin);
	in();
	deal();
	p();
	return 0;
}
int main(){;}
int xlm=Main();