玄关求条 原数据10pts Hack全对

#include<bits/stdc++.h>
#define int long long
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define inf 1000000000000000000
using namespace std;
const int N=1e5+99;
int n,m;
vector<int>e[N],r[N];
int a[N],rnk[N];
int f[N];
bitset<N>vis;
void dfs(int u,int maxx){
	if(f[u]){
		return;
	}
	f[u]=maxx;
	for(auto v:r[u]){
		if(f[v]){
			continue;
		}
		dfs(v,maxx);
	}
}
signed main(){
	fst;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		rnk[a[i]]=i;
	}
	for(int i=1;i<=m;i++){
		int u,v,x;
		cin>>u>>v>>x;
		e[u].push_back(v);
		r[v].push_back(u);
		if(x==2){
			e[v].push_back(u);
			r[u].push_back(v);
		}
	}
	auto bfs=[&](int s,vector<int>*e){
		queue<int>q;
		q.push(s);
		vis.reset();
		vis[s]=1;
		while(q.size()){
			int u=q.front();
			f[u]+=s;
			q.pop();
			for(auto v:e[u]){
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	};
	bfs(1,e);
	bfs(n,r);
	for(int i=1;i<=n;i++){
		if(f[i]<n+1){
			f[i]=inf;
		}else{
			f[i]=0;
		}
	}
	sort(a+1,a+1+n,greater<int>());
	for(int i=1;i<=n;i++){
		if(f[i]!=inf&&a[i]>f[rnk[a[i]]]){
			dfs(rnk[a[i]],a[i]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(f[rnk[a[i]]]==inf){
			continue;
		}
		ans=max(ans,f[rnk[a[i]]]-a[i]);
	}
	cout<<ans<<endl;
	return 0;
}