两个月前自己的做法，时间复杂度算了算只有O(m),个人觉得正确性假掉了，求hack或证明

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
int n,m,mx,mn[100010],pz[100010];
bool o[100010],l[100010],b[100010];
vector<int> vz[100010],vf[100010];
void DFSF(int p)
{
	if(o[p])
	{
		return;
	}
	o[p] = 1;
	for(int i = 0;i < vz[p].size();i++)
	{
		DFSF(vz[p][i]);
	}
}
int MIN(int p)
{
	if(b[p] == 1)
	{
		return mn[p];
	}
	b[p] = 1;
	if(o[p])
	{
		for(int i = 0;i < vf[p].size();i++)
		{
			MIN(vf[p][i]);
			mn[p] = min(mn[p],mn[vf[p][i]]);
		}
		mx = max(pz[p] - mn[p],mx);
	}else{
		mn[p] = 103;
		return 103;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		cin >> pz[i];
		mn[i] = pz[i];
	}
	int x,y,z;
	for(int i = 1;i <= m;i++)
	{
		cin >> x >> y >> z;
		if(z == 1)
		{
			vz[x].push_back(y);
			vf[y].push_back(x);
		}else{
			vz[x].push_back(y);
			vz[y].push_back(x);
			vf[x].push_back(y);
			vf[y].push_back(x);
		}
	}
	DFSF(1);
	MIN(n);
	cout << mx;
	return 0;
}