Description：

给定一张无向图，每个点有点权，每条边有边权，两个人轮流选择点，若一条边的两端点被选择则这条边被选择，两人都想自己的得分 $-$ 对手的得分最大，求最终先手得分 $-$ 后手得分。

$1\le n \le 10000$

Solution：

这道题有一个重要的特性就是最终得分是两人相减，于是我们就可以把边权除以二放到两个点上，这样如果这条边被两个人选了，那么就消掉了，否则会加上。于是一个点如果被选，那么会得到这个点的点权加所有与他相邻的边的权值的二分之一，否则会失去这些权值，于是先预先减去所有价值，然后把每个点的权值乘二两人轮流选。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 10010

#define MAXM 100010

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int val[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)val[i] = read();

	int sum = 0;

	for(int i = 1;i <= n;++i)sum -= val[i];

	for(int i = 1;i <= n;++i)val[i] *= 2;

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		a = read();b = read();c = read();

		sum -= c;val[a] += c;val[b] += c;

	}

	sort(val + 1,val + 1 + n);

	int ans = 0;

	for(int i = n;i >= 1;i -= 2)ans += val[i];

	cout << ans + sum << endl;

	return 0;

}