写了个类似于SPFA的东西，思路是维护从每个点开始到n的路径中最大值，复杂度应该可以跑到O（n2），所以我加了一个随机访问顺序，然后就过了。可是，当我把随机化删除以后，还能过。非常奇怪。

#include<bits/stdc++.h>
using namespace std;

struct node {
  int u, v, w;
} E[500010];
struct edge {
  int to, nxt;
} e[1000010];
int cnt, head[200010], n, m;
int a[200010], dis[200010];
bool gett[200010], vis[200010];
void dfs(int u) {
  gett[u] = 1;
  for(int i = head[u]; i; i = e[i].nxt) if(!gett[e[i].to])
    dfs(e[i].to);
}
void bfs() {
  priority_queue<pair<int, int> > q;
  for(int i = 1; i <= n; ++i) dis[i] = a[i];
  q.emplace(dis[n], n);
  while(!q.empty()) {
    int t = q.top().second;
    q.pop();
    for(int i = head[t]; i; i = e[i].nxt) {
      int v = e[i].to;
      if((vis[v] && dis[v] >= dis[t]) || !gett[v]) continue;
      else {
        dis[v] = max(dis[v], dis[t]);
        vis[v] = 1;
        q.emplace(dis[v], v);
      }
    }
  }
}
void add(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt;
}
int main() {
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) cin >> a[i];
  for(int i = 1; i <= m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    add(u, v);
    if(w == 2) add(v, u);
    E[i] = {u, v, w};
  }
  dfs(1);
  memset(e, 0, sizeof(e));
  memset(head, 0, sizeof(head));
  cnt = 0;
  for(int i = 1; i <= m; ++i) {
    add(E[i].v, E[i].u);
    if(E[i].w == 2) add(E[i].u, E[i].v);
  }
  bfs();
  int ans = 0;
  for(int i = 1; i <= n; ++i) if(gett[i]) ans = max(ans, dis[i] - a[i]);
  cout << ans << endl;
  return 0;
}