rt……莫名其妙连ACwing上加强数据都过了……并且我看题解里好像没这种做法……

（码风奇怪…不喜轻喷……）

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
const int maxn=1e5+10,INF=0x3f3f3f3f;

template <typename T> void read(T &x){
	x=0;char c=getchar();int f=1;
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
template <typename T> void write(T x){
	if(x<0){ x=-x;putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

int n,m,val[maxn],l[maxn],r[maxn],vis[maxn];
vector<int>G[maxn],H[maxn];
void add1(int u,int v){
	G[u].push_back(v);
}
void add2(int u,int v){
	H[v].push_back(u);
}
void dfs1(int u,int f){
	l[u]=min(val[u],l[f]);
	vis[u]=1;
	for(auto v:G[u]){
		l[v]=min(l[u],l[v]);
		if(vis[v]) continue;
		dfs1(v,u);
	}
}
void dfs2(int u,int f){
	r[u]=max(val[u],r[f]);
	vis[u]=1;
	for(auto v:H[u]){
		r[v]=max(r[v],r[u]);
		if(vis[v]) continue;
		dfs2(v,u);
	}
}
int main(){
	read(n);read(m);
	for(int i=1;i<=n;i++) read(val[i]);
	for(int i=1;i<=m;i++){
		int u,v,w;
		read(u);read(v);read(w);
		add1(u,v);add2(u,v);
		if(w==2){
			add1(v,u);add2(v,u);
		}
	}
	memset(l,0x3f,sizeof(l));l[1]=val[1];
	dfs1(1,1);
	memset(r,0,sizeof(r));r[n]=val[n];
	memset(vis,0,sizeof(vis));
	dfs2(n,n);
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,r[i]-l[i]);
	}
	write(ans);
	return 0;
}

9 10
4 3 2 1 5 7 8 9 6
1 2 1
2 3 1
3 4 1
4 2 1
2 5 1
5 6 1
6 7 1
7 8 1
8 6 1
6 9 1

（一开始被这组数据hack掉了，然后“ l[v]=min(l[u],l[v]); ”这一句放到“ if(vis[v]) continue; ”上面就过了……）