rt,求助，回复必关注

#include<bits/stdc++.h>
using namespace std;
#define _for for(int i=1;i<=n;i++)
#define pii pair<int,int>
const int N=1e5+5;
const int M=5e5+5;
inline int read(){
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    int t=0;
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=getchar();
    }
    return t;
}

int n,m,u,v,z;
pii wei[N],wei2[N];
//建立原图
struct node{
    int fr,to,next;
}e[M*2];
int pre[M*2],k;
inline void add(int fr,int to){
    k++;
    e[k].fr=fr;
    e[k].to=to;
    e[k].next=pre[fr];
    pre[fr]=k;
    return ;
}
//在原图中求点双连通分量
int dfn[N],num,low[N],my_g[N],cntg;
bool in_stack[N];

stack<int> s;
inline void tarjan(int x){
    low[x]=dfn[x]=++num;
    s.push(x);
    in_stack[x]=true;
    for(int i=pre[x];i!=0;i=e[i].next){
        int y=e[i].to;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(in_stack[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        cntg++;
        int minn=wei[x].first,maxn=wei[x].first;//wei存的是原图的点的值，其实不用pair
        while(s.top()!=x){
            minn=min(wei[s.top()].first,minn);//一个点双连通分量只有其中的最大值最小值有用
            maxn=max(wei[s.top()].first,maxn);
            in_stack[s.top()]=false;
            my_g[s.top()]=cntg;
            s.pop();
        }
        s.pop();
        in_stack[x]=false;
        my_g[x]=cntg;//my_g 表示这个点在新图中的对应
        wei2[cntg].first=minn;
        wei2[cntg].second=maxn;//wei2表示新的图中的点的值
    }
    return ;
}
//建立新的图
node e2[M*2];
int pre2[M*2],k2;
inline void add2(int fr,int to){
    k2++;
    e2[k2].fr=fr;
    e2[k2].to=to;
    e2[k2].next=pre2[fr];
    pre2[fr]=k2;
    return ;
}
//用于求答案的dfs
int ans=0;
inline void dfs(int pos,int minn,int tmp){
    minn=min(wei2[pos].first,minn);
    tmp=max(tmp,wei2[pos].second-minn);
    if(pos==my_g[n]){
        ans=max(ans,tmp);
        return ;
    }
    else{
        for(int i=pre2[pos];i!=0;i=e2[i].next) dfs(e2[i].to,minn,tmp);
    }
    return ;
}

int main(){
    n=read();
    m=read();
    _for{
        wei[i].first=read();
        wei[i].second=-1;
    }
    for(int i=1;i<=m;i++){
        u=read();
        v=read();
        z=read();
        if(z==1) add(u,v);
        else{
            add(v,u);
            add(u,v);
        }
    }
    //求点双连通分量
    _for{
        if(dfn[i]!=0) continue;
        else tarjan(i);
    }
    //缩点建立新的图
    for(int i=1;i<=k;i++){
        if(my_g[e[i].to]==my_g[e[i].fr]) continue;
        else{
            add2(my_g[e[i].fr],my_g[e[i].to]);
        }
    }
    //跑dfs求答案
    dfs(my_g[1],0x3f3f3f3f,0);
    printf("%d\n",ans);
    return 0;
}