10分，吐了（我相信看了我的代码的人会感到ex的） tarjan+spfa

救救孩子！

#include<bits/stdc++.h>
using namespace std;
int cnt,head[10000005],hhead[1000005],cntt;
int dfn[1000005],low[10000005],id[1000005],t,l,ld,sum[1000005],usum[1000005];
int n,m,x,y,z,a[1000005];
int beg,fin,sss[10000005],ssb[1000005];
bool f[1000005],fs[1000005];
stack<int> s;
queue<int> q;
struct edge
{
	int next,to;
}e[1000005],ee[10000005];
int read()
{
    int w=1,q=0;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return w*q;
}
void add(int x,int y)
{
	cnt++;
	e[cnt].next=head[x];
	e[cnt].to=y;
	head[x]=cnt;
}
void addd(int x,int y)
{
	cntt++;
	ee[cntt].next=hhead[x];
	ee[cntt].to=y;
	hhead[x]=cntt;
}
void tarjan(int u)
{
	dfn[u]=low[u]=++t;
	s.push(u);
	f[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(f[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		l++;
		usum[l]=1e9;
		while(f[u])
		{
			id[s.top()]=l;
			sum[l]=max(sum[l],a[s.top()]);
			usum[l]=min(usum[l],a[s.top()]);
			f[s.top()]=0;
			s.pop();
		}
	}
	return;
}
void spfa()
{
	q.push(beg);
	fs[beg]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=ee[i].next)
		{
			int v=ee[i].to;
			sss[v]=max(sss[v],sss[u]);
			ssb[v]=min(ssb[v],ssb[u]);
			if(!f[v]) q.push(v);
			f[v]=1;
		}
	}
	return;
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=m;i++)
	{
		x=read();
		y=read();
		z=read();
		add(x,y);
		if(z==2) add(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
			tarjan(i);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=e[j].next)
		{
			if(id[i]==id[e[j].to]) continue;
			addd(id[i],id[e[j].to]);
		}
	}
	beg=id[1];
	fin=id[n];
	if(beg==fin)
	{
		cout<<sum[id[1]]-a[1]<<endl;
		return 0;
	}
	for(int i=1;i<=l;i++) sss[i]=sum[i],ssb[i]=usum[i];
	spfa();
	cout<<max(sss[fin]-ssb[fin],0)<<endl;
	return 0;
}