按照DP思路结果样例都没过..

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
inline int read(){
	int x=0,f=1,ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;	ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch^48;ch=getchar();}
	return f*x;
}
int n=read(),m=read(),f[N],mi[N],w[N];
vector<int> G[N];
inline void dfs(int x,int minx,int pre){//pre:前驱节点 
	int fg=1;
	minx=min(minx,w[x]);
	if(mi[x]>minx) mi[x]=minx,fg=0;
	int mx=max(f[pre],w[x]-minx);
	if(f[x]<mx) f[x]=mx,fg=0;
	if(fg) return;
	for(int i=0;i<G[x].size();i++) dfs(G[x][i],minx,x);
}
int main(){
//	memset(mi,0x7fffffff,sizeof(mi));
	for(int i=0;i<N;i++) mi[i]=0x7fffffff;
	for(int i=1;i<=n;i++) w[i]=read();
	for(int i=1,a,b,c;i<=m;i++){
		a=read(),b=read(),c=read();
		if(!c&1) G[b].push_back(a);
		G[a].push_back(b);
	} 
	dfs(1,0x7fffffff,0);
	printf("%d\n",f[n]);
	return 0;
}