#include<bits/stdc++.h> using namespace std; int n,m,w[100001],maxx=0,minn; vector<int>g[100001]; set<int>f[100001]; inline void read(int& a) { int s = 0, w = 1; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } a = s * w; } inline void dfs(int x,int yu) { f[yu].insert(x); maxx=max(maxx,w[x]-w[yu]); for(int i=0; i<g[x].size(); ++i) { if(f[yu].count(g[x][i])==0) { //f[yu].insert(g[x][i]); dfs(g[x][i],yu); } } } int main() { read(n); read(m); for(int i=1; i<=n; ++i) { read(w[i]); minn=max(w[i],minn); } for(int i=1; i<=m; ++i) { int x,y,z; read(x);read(y);read(z); g[x].push_back(y); if(z==2) g[y].push_back(x); } for(int i=1; i<=n; ++i) { int ffff=maxx; if(minn-w[i]<=maxx) continue; dfs(i,i); if(i!=1) if(f[1].count(i)==0||f[i].count(n)==0) maxx=ffff; } printf("%d",maxx); return 0; }