#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3fLL;
int v[N], num[N], low[N];
int c[N], cnt, dfn;
int val[N][2];
int idn[N];
stack<int> stk;
vector<int> a[N];
vector<int> now[N];
void dfs(int u) {
    stk.push(u);
    num[u] = low[u] = ++dfn;
    for (int i = 0; i < a[u].size(); i++) {
        int v = a[u][i];
        if (!num[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (!c[v]) {
            low[u] = min(low[u], num[v]);
        }
    }
    if (num[u] == low[u]) {
        cnt++;
        while (1) {
            int p = stk.top();
            stk.pop();
            c[p] = cnt;
            val[cnt][0] = max(val[cnt][0], v[p]);
            val[cnt][1] = min(val[cnt][1], v[p]);
            if (p == u)
                break;
        }
    }
}
signed main() {
    int n, m;
    cin>>n>>m;
    for (int i = 1; i <= n; i++) {
        cin>>v[i];
        val[i][1] = INF;
    }
    vector<array<int, 3>> b;
    for (int i = 1; i <= m; i++) {
        int u, v, z;
        cin>>u>>v>>z;
        b.push_back({u, v, z});
        a[u].push_back(v);
        if (z == 2)
            a[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!num[i])
            dfs(i);
    }
    
    for (int i = 0; i < m; i++) {
        int u = b[i][0], v = b[i][1], z = b[i][2];
        if (c[u] == c[v])
            continue;
        now[c[u]].push_back(c[v]);
        idn[c[v]]++;
        if (z == 2) {
            idn[c[u]]++;
            now[c[v]].push_back(c[u]);
        }
    }
    queue<int> q;
    q.push(c[1]);
    vector<array<int, 2>> dp(cnt + 1, {0, INF});//ans, min
    dp[c[1]] = {0, val[c[1]][1]};
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < now[u].size(); i++) {
            int v = now[u][i];
            int mmin = min(dp[u][1], val[v][1]);
            int ans = max(dp[u][0], val[v][0] - mmin);
            dp[v] = {ans, mmin};
            idn[v]--;
            if (idn[v] == 0)
                q.push(v);
        }
    }
    cout<<dp[c[n]][0];
    return 0;
}

我这样写可能连n点都跑不动，但是却能ac

数据：
输入
4 3
1 2 3 4
1 2 1
2 4 1
3 2 1
错误输出
0
正确输出
3