记录编号	80213	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	Mongo	是否通过	通过
代码语言	C++	运行时间	0.442 s
提交时间	2013-11-06 21:35:02	内存使用	5.38 MiB

//#define lgg
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#ifdef lgg
#include <iostream>
#endif
using namespace std;
typedef vector<long>::iterator it;
ifstream in("trade.in"); ofstream out("trade.out");
vector<long> b[100001];
long N, M;
int f[100001], w[100001];
bool inq[100001], ck[100001];
void inline read()
{
	in >> N >> M;
	for(long i(1); i<=N; ++i)
	{
		in >> w[i]; f[i]=w[i];
	}
	long x, y; int z;
	for(long i(1); i<=M; ++i)
	{
		in >> x >> y >> z;
		if(z==1)
			b[y].push_back(x);
		else
		{
			b[y].push_back(x); b[x].push_back(y);
		}
	}
}
void inline Espfa()
{
	queue<long> q;
	for(long k(N); k>=1; --k)
	{
		if(ck[k]==0)continue;
		q.push(k);
		for(it i(b[k].begin()); i!=b[k].end(); ++i)
			q.push(*i);
		while(!q.empty())
		{
			long root(q.front()); q.pop();
			for(it i(b[root].begin()); i!=b[root].end(); ++i)
				if(f[root]>f[*i])
				{
					f[*i]=f[root];
					q.push(*i);
				}
		}
	}
}
void check(long root)
{
	if(ck[root]==1)return;
	ck[root]=1;
	for(it i(b[root].begin()); i!=b[root].end(); ++i)
		check(*i);
	return;
}
int main()
{
	read();
	check(N);
	Espfa();
	int ans(-10000);
	for(long i(2); i<N; ++i)
		ans=max(ans, f[i]-w[i]);
	#ifdef lgg
	for(long i(1); i<=N; ++i)
		out << "点" << i << "能走到的最大价值为" << f[i] << "，其自己的价值为" << w[i] << endl;
	#endif
	out << ans << endl;
	return 0;
}