我的思路是 Tarjan 缩点，然后 DFS 删去 1 到不了的边。然后 Topo Dp,但是只有 10 pts;

/*
	Name: [NOIP2009 提高组] 最优贸易
	Copyright: LG 1073
	Author: Isshiki·Iroha
	Date: 25/09/21 14:16
	Description: Tarjan(SCC) + Topo + Dp
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace Mashiro {
	char buf[1<<18],*p1=buf,*p2=buf;
	inline int getc() {
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++;
	}
#define getc() getchar()
	template<typename T>inline void read(T& x) {
		x=0;
		int f=1;
		char ch=getc();
		while(!isdigit(ch)) {
			if(ch=='-')f=~f+1;
			ch=getc();
		}
		while (isdigit (ch)) {
			x=(x<<3)+(x<<1)+(ch^48);
			ch=getc();
		}
		x*=f;
	}
	template <typename T,typename... Args> inline void read(T& x, Args&... args) {
		read(x);
		read(args...);
	}
	char buffer[1<<18];
	int p11=-1;
	const int p22=(1<<18)-1;
	inline void flush() {
		fwrite(buffer,1,p11+1,stdout),p11=-1;
	}
	inline void putc(const char &x) {
		if (p11==p22) flush();
		buffer[++p11]=x;
	}
	template<typename T>inline void write(T x) {
		static int buf[40],top=0;
		if(x<0)putc('-'),x=~x+1;
		while(x)buf[++top]=x%10,x/=10;
		if(top==0)buf[++top]=0;
		while (top) putc(buf[top--]^48);
		putc(' ');
		flush();
	}
	template <typename T,typename... Args> inline void write(T x, Args... args) {
		write(x);
		write(args...);
	}
}
template<typename T>
T Min(T a,T b){
	return a>b?b:a;
}
template<typename T>
T Max(T a,T b){
	return a<b?b:a;
}
using namespace Mashiro;
const int maxn=1e5+10;
const int maxm=1e6+10;
//All
int n,m,st,et;
int price[maxn];
//All

//Map
int head[maxn],tot;
struct node{
	int u,v,nxt;
}kano[maxm];
inline void add_kano(int u,int v){
	++tot;
	kano[tot].nxt=head[u];
	kano[tot].v=v;
	kano[tot].u=u;
	head[u]=tot;
}
//Map

//Tarjan
int dfn[maxn],low[maxn],times;
int Instack[maxn],St[maxn],top;
int scc_cnt;
int scc_max_price[maxn],scc_min_price[maxn];
int scc_belong[maxn];
inline void Tarjan(int u){
	dfn[u]=low[u]=++times;
	Instack[u]=1;
	St[++top]=u;
	for(int i(head[u]);i;i=kano[i].nxt){
		int v=kano[i].v;
		if(!dfn[v]){
			Tarjan(v);
			low[u]=Min(low[u],low[v]);
		}
		else if(Instack[v]){
			low[u]=Min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		int v;
		++scc_cnt;
		do{
			v=St[top--];
			Instack[v]=0;
			scc_max_price[scc_cnt]=Max(scc_max_price[scc_cnt],price[v]);
			scc_min_price[scc_cnt]=Min(scc_min_price[scc_cnt],price[v]);
			if(v==1)st=scc_cnt;
			if(v==n)et=scc_cnt;
			scc_belong[v]=scc_cnt;
		}while(v!=u);
	}
}
//Tarjan
int vis[maxn];
//dfs
void dfs(int u){
	if(vis[u])return;
	vis[u]=1;
	for(int i(head[u]);i;i=kano[i].nxt){
		int v=kano[i].v;
		dfs(v);
	}
}
//dfs

//Topo
int In[maxn],f_max[maxn],f_min[maxn];
inline void Topo(){
	queue<int>q;
	for(int i(1);i<=n;++i){
		if(In[i]==0&&vis[i]==1){
			q.push(i);
		}
		f_max[i]=scc_max_price[i];
		f_min[i]=scc_min_price[i];
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i(head[u]);i;i=kano[i].nxt){
			int v=kano[i].v;
			--In[v];
			f_max[v]=Max(f_max[v],f_max[u]);
			f_min[v]=Min(f_min[v],f_min[u]);
			if(In[v]==0)q.push(v);
		}
	}
}
//Topo
int main() {
	read(n,m);
	memset(scc_min_price,0x3f,sizeof scc_min_price);
	for(int i(1);i<=n;++i)read(price[i]);
	for(int i(1),u,v,t;i<=m;++i){
		read(u,v,t);
		add_kano(u,v);
		if(t==2)add_kano(v,u);
	}
	for(int i(1);i<=n;++i){
		if(!dfn[i]){
			Tarjan(i);
		}
	}
	//write(scc_cnt);
	memset(head,0,sizeof head);
	int ttot=tot;
	tot=0;
	for(int i(1),Tx,Ty;i<=ttot;++i){
		Tx=scc_belong[kano[i].u];
		Ty=scc_belong[kano[i].v];
		if(Tx==Ty)continue;
		add_kano(Tx,Ty);
	}
	
	dfs(st);
	memset(head,0,sizeof head);
	ttot=tot;
	tot=0;
	for(int i(1),Tx,Ty;i<=ttot;++i){
		Tx=scc_belong[kano[i].u];
		Ty=scc_belong[kano[i].v];
		if(Tx==Ty)continue;
		if(vis[Tx]==0||vis[Ty]==0)continue;
		add_kano(Tx,Ty);
		++In[Ty];
	}
	//write(tot);
	//write(st,et);
	//write(scc_max_price[st],scc_min_price[st]);
	Topo();
	//write(f_max[st],f_min[st]);
	write(Max(f_max[et]-f_min[et],0));
	return 0;
}
/*
5 5
20 70 0 98 80
1 2 1
3 2 1
2 5 2
2 4 2
5 4 2
*/