#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],idx[100005],cnt,colnum,col[100005],minx[100005],maxx[100005];
vector<int>g[100005];
vector<int>rg[100005];
vector<int>dg[100005];
bool vis[100005];
void dfs(int x){
    vis[x]=true;//标记
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(!vis[v])
            dfs(v);//深搜
    }
    idx[++cnt]=i;//标点
}
void rdfs(int x,int c){//染色
    vis[x]=true;//标记
    col[x]=c;//将x点染色为c
    for(int i=0;i<rg[x].size();i++){
        int v=g[x][i];
        if(!vis[v])
            dfs(v,c);
    }
}
int ddfs(int x,int mix,int mxx){//深搜遍历求解
    if(x==col[idx[n]])//到重点了
        return mxx-mix;
    int ans=0;
    for(int i=0;i<dg[x].size();i++){//取最大
        int v=dg[x][i];
        ans=max(ans,dfs(v,min(mix,minx[v]),max(mxx,maxx[v])));
    }
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1,u,v,op;i<=m;i++){//存图
        cin>>u>>v>>op;
        if(op==1){
            g[u].push_back(v);
            g[v].push_back(u);
        }else{
            g[u].push_back(v);
            g[v].push_back(u);
            rg[u].push_back(v);
            rg[v].push_back(u);
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis(i)){
            dfs(i);//若未标记过，则标点
        }
    }
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=cnt;i++){
        if(!rdfs(idx[i])){
            rdfs(idx[i],++colnum);//若未标记过，则给此点染色
        }
    }
    for(int i=1;i<=n;i++){//存缩点后的图
        for(int j=0;j<g[i].size();j++){
            int v=g[i][j];
            if(col[idx[i]]!=col[idx[v]]){
                dg[col[idx[i]]].push_back(col[idx[v]]);
            }
        }
    }
    memset(minx,0x3f,sizeof(minx));
    for(int i=1;i<=n;i++){//取缩的每个点的水晶球价格的最大最小
        minx[col[idx[i]]]=min(minx[col[idx[i]]],a[i]);
        maxx[col[idx[i]]]=max(maxx[col[idx[i]]],a[i]);
    }
    cout<<ddfs(col[idx[1]],minx[col[idx[1]]],maxx[col[idx[1]]]);
    return 0;
}

强连通缩点+dfs暴力求解，样例未过qwq