[国家集训队] 阿狸和桃子的游戏-526互联

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 1e6 + 10;

int n, m;
int k[N], a, b, c;
int val[N];

//如果一条边的两端点被同一个人选了，那么产生边权的贡献
//把边权均分到两端点上，每个端点加上 c / 2
//如果这条边被同一个 选了，那么边权贡献为c / 2 + c / 2 = c
//否则c / 2 - c / 2 = 0 

signed main(){
//	freopen("1.in", "r", stdin);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> k[i];
		val[i] = k[i] * 2;
	}
	for(int i = 1; i <= m; i++){
		cin >> a >> b >> c;
		val[a] += c;
		val[b] += c;
	}
	
	sort(val + 1, val + 1 + n, greater <int> ());
	int suma = 0, sumb = 0;
	for(int i = 1; i <= n; i++){
		if(i % 2){
			suma += val[i];
		}else{
			sumb += val[i];
		}
	}
	int ans = (suma - sumb) / 2;
	cout << ans << "\n";
}