rt，#3 一直过不去。

还是我哪里脑抽写错了

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e5+10,M=5e5+10,INF=0x3f3f3f3f; int cnt,cnt2,a[N],h[N],h2[N],mx[N],mn[N]; bool vis[N];
struct Edge { int v,w,nxt; }e[2*M],e2[2*M];
void add(int u,int v,int w) { e[++cnt]=(Edge){v,w,h[u]},h[u]=cnt; }
void add2(int u,int v,int w) { e2[++cnt2]=(Edge){v,w,h2[u]},h2[u]=cnt2; }
void SPFA(int s) {
  memset(mn,0x3f,sizeof(mn));
  queue<int>q; q.push(s),vis[s]=true;
  while(!q.empty()) {
  	int u=q.front(); q.pop();
  	vis[u]=false;
  	for(int i=h[u];i;i=e[i].nxt) {
  	  int v=e[i].v,w=e[i].w;
  	  if(mn[v]>min(mn[u],w)) {
  	    mn[v]=min(mn[u],w);
  	    if(!vis[v]) vis[v]=true,q.push(v);
	  }
  	}
  }
}
void SPFA2(int s) {
  memset(vis,false,sizeof(vis));
  queue<int>q; q.push(s),vis[s]=true;
  while(!q.empty()) {
  	int u=q.front(); q.pop();
  	vis[u]=false;
  	for(int i=h2[u];i;i=e2[i].nxt) {
  	  int v=e2[i].v,w=e2[i].w;
  	  if(mx[v]<max(mx[u],w)) {
  	    mx[v]=max(mx[u],w);
  	    if(!vis[v]) vis[v]=true,q.push(v);
	  }
  	}
  }
}
int main() {
  int n,m; scanf("%d %d",&n,&m);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  while(m--) {
  	int x,y,z; scanf("%d %d %d",&x,&y,&z);
  	if(z==1) add(x,y,a[y]),add2(y,x,a[x]);
  	else add(x,y,a[y]),add(y,x,a[x]),add2(x,y,a[y]),add2(y,x,a[x]);
  }
  SPFA(1),SPFA2(n);
  int ans=0;
  for(int i=1;i<=n;i++) ans=max(ans,mx[i]-mn[i]);
  printf("%d",ans);
  return 0;
}