trade.cpp

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,m;
bool vis[100010];
int price[100100],minp[100100],maxp[100100];
vector<int> Edge[500500],revEdge[500500];
void dfs1(int i,int minn){
	minp[i]=min(price[i],minn);
	vis[i]=true;
	for(int k=0;k<Edge[i].size();k++)
		if(!vis[Edge[i][k]])
			dfs1(Edge[i][k],minp[i]);
}
void dfs2(int i,int maxn){
	maxp[i]=max(price[i],maxn);
	vis[i]=true;
	for(int k=0;k<revEdge[i].size();k++)
		if(!vis[revEdge[i][k]])
			dfs2(revEdge[i][k],maxp[i]);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>price[n];
	int x=0,y=0,z=0;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		Edge[x].push_back(y);
		revEdge[y].push_back(x);
		if(z==2){
			Edge[y].push_back(x);
			revEdge[x].push_back(y);
		}
	}
	dfs1(1,21474836);
	memset(vis,false,sizeof(vis));
	dfs2(n,-1);
	int maxn=-1;
	for(int i=1;i<=m;i++)
		maxn=max(maxn,maxp[i]-minp[i]);
	cout<<maxn;
	return 0;
}