#include<bits/stdc++.h> #define int long long using namespace std; int n,m,ans; int a[500005]; struct node { vector<int> to; vector<bool> vis; } g1[500005],g2[500005]; int dis1[500005],dis2[500005]; void dfs1(int v) { for (int i=0; i<g1[v].to.size(); i++) { if (dis1[v]<dis1[g1[v].to[i]]) { dis1[g1[v].to[i]]=dis1[v]; dfs1(g1[v].to[i]); } if (g1[v].vis[i]==0) { g1[v].vis[i]=1; dfs1(g1[v].to[i]); } } } void dfs2(int v) { for (int i=0; i<g2[v].to.size(); i++) { if (dis2[v]>dis2[g2[v].to[i]]) { dis2[g2[v].to[i]]=dis2[v]; } if (g2[v].vis[i]==0) { g2[v].vis[i]=1; dfs2(g2[v].to[i]); } } } signed main() { /*ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);*/ cin>>n>>m; for (int i=1; i<=n; i++) { cin>>a[i]; } for (int i=1; i<=m; i++) { int x,y,z; cin>>x>>y>>z; if (z==1) { g1[x].to.push_back(y); g2[y].to.push_back(x); g1[x].vis.push_back(0); g2[y].vis.push_back(0); } else { g1[x].to.push_back(y); g1[y].to.push_back(x); g2[y].to.push_back(x); g2[x].to.push_back(y); g1[x].vis.push_back(0); g1[y].vis.push_back(0); g2[y].vis.push_back(0); g2[x].vis.push_back(0); } } for (int i=1; i<=n; i++) { dis1[i]=dis2[i]=a[i]; } dfs1(1); dfs2(2); for (int i=1; i<=n; i++) { ans=max(ans,dis2[i]-dis1[i]); } cout<<ans; return 0; }