rt，思路是先缩点，先对强连通分量内取最大值，然后考虑跨强连通分量的点

从n所在强连通分量开始dfs，到1所在的强连通分量停止，不断更新最大值和最小值，最后输出极差

求hack数据，下载数据太大手调不了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,w[N],id[N],insta[N],sta[N<<1],low[N],dfn[N],cnt,tot,top,sma[N],smi[N],maxx=-0x3f3f3f3f,minn=0x3f3f3f3f,ans;
vector<int>v[N],vv[N];
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-48;ch=getchar();}
	return s*w;
}
inline void tarjan(int u)
{
	dfn[u]=low[u]=++cnt;
	insta[u]=1;
	sta[++top]=u;
	for(int t:v[u])
	{
		if(!dfn[t])
		{
			tarjan(t);
			low[u]=min(low[u],low[t]);
		}
		else if(insta[t])
		{
			low[u]=min(low[u],dfn[t]);
		}
	}
	if(dfn[u]==low[u])
	{
		id[u]=++tot;
		sma[tot]=-0x3f3f3f3f;
		smi[tot]=0x3f3f3f3f;
		while(sta[top]!=u)
		{
			int tmp=sta[top];
			sta[top--]=0;
			insta[tmp]=0;
			id[tmp]=tot;
			sma[tot]=max(sma[tot],w[tmp]);
			smi[tot]=min(smi[tot],w[tmp]);
		}
		insta[u]=0;
		sta[top--]=0;
		sma[tot]=max(sma[tot],w[u]);
		smi[tot]=min(smi[tot],w[u]);
		ans=max(ans,sma[tot]-smi[tot]);
	}
}
inline void dfs(int p)
{
	maxx=max(maxx,sma[p]);
	minn=min(minn,smi[p]);
	if(p==id[1])
	{
		ans=max(ans,maxx-minn);
		return;
	}
	for(int t:vv[p])
	{
		dfs(t);
	}
	return;
}
map<pair<int,int>,bool>ma;
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)w[i]=read();
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read(),z=read();
		if(z==1)
		{
			if(ma.find(make_pair(x,y))!=ma.end())continue;
			v[x].push_back(y);
			ma[make_pair(x,y)]=1;
		}
		else
		{
			if(ma.find(make_pair(x,y))==ma.end()){v[x].push_back(y),ma[make_pair(x,y)]=1;}
			if(ma.find(make_pair(y,x))==ma.end()){v[y].push_back(x),ma[make_pair(y,x)]=1;}
		}
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])tarjan(i);
	ma.clear();
	for(int i=1;i<=n;i++)
	{
		for(int t:v[i])
		{
			if(id[t]!=id[i])
			{
				if(ma.find(make_pair(id[t],id[i]))==ma.end())
				{
					vv[id[t]].push_back(id[i]);
					ma[make_pair(id[t],id[i])]=1;
				}
			}
		}
	}
	dfs(id[n]);
	cout<<ans;
	return 0;
}