问题1225--自行车调度

1225: 自行车调度

[命题人 : ]
时间限制 : 2.000 sec  内存限制 : 512 MB

题目描述

n个点,m条边的无向带正权图(编号1到n).
每个点初始有a[i](0<=a[i]<=1e5,1<=i<=n)辆自行车,自行车管理员可以花费一个边权的代价移动一辆自行车从边的一端到另一端。
求自行车管理员所需的最小的代价使每个点自行车数量相等(无解输出-1)。

输入

第一行一个整数T表示数据组数。
对于每一组数据:
第一行两个整数n(1<=n<=500),m(0<=m<=1000),
第二行n个整数,第i个整数a[i](0<=a[i]<=1e5)表示第i个点初始的自行车数量,
接下去m行,每行三个整数x(1<=x<=n),y(1<=y<=n),w(0<=w<=1e5),表示一条x到y的无向边,边权为w。
保证Σn<=500,Σm<=1000

输出

对于每组数据输出一个整数表示答案。
每组数据的答案占一行。

样例输入 Copy

1
3 3
5 2 2
1 2 2
2 3 1
1 3 4

样例输出 Copy

5