思路：tarjan+拓扑排序+dp，第12,13个测试点是WA

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N=100010,M=1000010,inf=1e9+10;
int ver[N],to[N],nxt[N],idx,tmp[N],w[N][2],u[M/2],v[M/2],n,m,ans=0;
int dfn[N],low[N],scc,tot,stk[N],top,mk[N],f[N],d[N],dp[N][2];
bool pd[N][2];
void add(int x,int y){
    to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx;
}
int cmp(int a,int b,int c){
    if(c==1)return min(a,b);
    else return max(a,b);
}
void tarjan(int u){
    dfn[u]=low[u]=++tot;
    stk[++top]=u,mk[u]=1;
    for(int i=ver[u];i;i=nxt[i]){
        int tp=to[i];
        if(!dfn[tp]){
            tarjan(tp);
            low[u]=min(low[u],low[tp]);
        }else if(mk[tp])low[u]=min(low[u],dfn[tp]);
    }
    if(dfn[u]==low[u]){
        int cnt1=-inf,cnt2=inf,tp;scc++;
        while(stk[top+1]!=u){
            tp=stk[top--];
            f[tp]=scc;
            mk[tp]=0;
            cnt1=max(cnt1,tmp[tp]);
            cnt2=min(cnt2,tmp[tp]);
        }
        w[scc][0]=cnt1,w[scc][1]=cnt2;
    }
    return;
}
void topsort(int s,int p){
    queue<int>q;
    q.push(f[s]),dp[f[s]][p]=w[f[s]][p];
    while(q.size()){
        int t=q.front();q.pop();
        for(int i=ver[t];i;i=nxt[i]){
            int tp=to[i];
            d[tp]--;pd[tp][p]=1;
            dp[tp][p]=cmp(dp[t][p],w[tp][p],p);
            if(!d[tp])q.push(tp);
        }
    }
    return;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",tmp+i);
    }
    for(int i=1;i<=m;i++){
        int z;
        scanf("%d %d %d",u+i,v+i,&z);
        if(z==1)add(u[i],v[i]);
        else add(u[i],v[i]),add(v[i],u[i]);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    memset(ver,0,sizeof(ver));memset(to,0,sizeof(to));memset(nxt,0,sizeof(nxt));idx=0;
    for(int i=1;i<=m;i++)if(f[u[i]]!=f[v[i]])add(f[u[i]],f[v[i]]),d[f[v[i]]]++;
    topsort(1,1);
    memset(ver,0,sizeof(ver));memset(to,0,sizeof(to));memset(nxt,0,sizeof(nxt));idx=0;
    for(int i=1;i<=m;i++)if(f[u[i]]!=f[v[i]])add(f[v[i]],f[u[i]]),d[f[u[i]]]++;
    topsort(n,0);
    pd[f[1]][1]=pd[f[1]][0]=pd[f[n]][1]=pd[f[n]][0]=1;
    for(int i=1;i<=scc;i++)if(pd[i][1]&&pd[i][0])ans=max(ans,dp[i][0]-dp[i][1]);
    cout<<ans<<endl;
    return 0;
}