9215 - 最小代价

通过次数

0

提交次数

0

时间限制 : 1 秒
内存限制 : 128 MB

给出一幅由n个点m条边构成的无向带权图。 其中有些点是黑点,其他点是白点。 现在每个白点都要与他距离最近的黑点通过最短路连接(如果有很多个黑点,可以选取其中任意一个),我们想要使得花费的代价最小。请问这个最小代价是多少? 注意:最后选出的边保证每个白点到离它最近的黑点的距离仍然等于原图中的最短距离。

输入

第一行两个整数n,m; 第二行n 个整数,0表示白点,1 表示黑点; 接下来m 行,每行三个整数x,y,z,表示一条连接x和y 点,权值为z的边。

输出

如果无解,输出impossible;否则,输出最小代价。

样例

输入

5 7
0 1 0 1 0
1 2 11
1 3 1
1 5 17
2 3 1
3 5 18
4 5 3
2 4 5

输出

5