原题（我没过样例）

my code：

#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=1000005;
int a[N],n,m;
int h1[N],v1[M],nex1[M],d1[N],tot1=0;
int h2[N],v2[M],nex2[M],d2[N],tot2=0;
bool f[N];
void add1(int x,int y){
	nex1[++tot1]=h1[x];
	v1[tot1]=y;
	h1[x]=tot1;
}
void add2(int x,int y){
	nex2[++tot2]=h2[x];
	v2[tot2]=y;
	h2[x]=tot2;
}
void SPFA1(){
	memset(d1,0x7fffffff,sizeof(d1));
	memset(f,0,sizeof(f));
	f[1]=1;
	d1[1]=a[1];
	queue<int>qu;
	qu.push(1);
	while(qu.size()){
		int x=qu.front();
		qu.pop();
		f[x]=0;
		for(int i=h1[x];i;i=nex1[i]){
			int y=v1[i];
			if(d1[y]>min(a[y],d1[x])){
				d1[y]=min(a[y],d1[x]);
				if(!f[y]){
					qu.push(y);
					f[y]=1;
				}
			}
		}
	}
}
void SPFA2(){
	memset(d2,-0x7fffffff,sizeof(d2));
	memset(f,0,sizeof(f));
	f[n]=1;
	d2[n]=a[n];
	queue<int>qu;
	qu.push(n);
	while(qu.size()){
		int x=qu.front();
		qu.pop();
		f[x]=0;
		for(int i=h2[x];i;i=nex2[i]){
			int y=v2[i];
			if(d2[y]<max(a[y],d2[x])){
				d2[y]=max(a[y],d2[x]);
				if(!f[y]){
					qu.push(y);
					f[y]=1;
				}
			}
		}
	}
}
int main(){
	int maxn=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		if(z==1){
			add1(x,y);
			add2(y,x);
		}
		else{
			add1(x,y);
			add1(y,x);
			add2(x,y);
			add2(y,x);
		}
	}
	SPFA1();
	SPFA2();
	for(int i=1;i<=n;i++){
		if(d2[i]-d1[i]>maxn){
			maxn=d2[i]-d1[i];
		}
	}
	cout<<maxn<<endl;
}