IITWPC4I - Petya and the Road Repairs


Petya is the mayor of a city named Mayapur. In the morning, everybody likes to drink hot tea in bed, and the citizens need milk to take with their tea. For this purpose, they should be able to reach at least some milkman in the city. There are m bi-directional roads in the city but all of them are currently unrepaired, hence not in a state of use.
Petya cares about his city a lot and intends to repair some of these roads, so that every citizen is connected to at least one milkman. For repairing each road he needs to pay a cost. He would like to minimize the cost of this project. Note that a milkman does not need to go to some other milkman for milk as he can take milk from himsaelf. 

Help Petya in finding out the minimum cost needed to repair the roads in the given way. If it is not possible for a citizen to connect to any of the milkmen, output "impossible" (without quotes).

Input

The first line contains T: the number of test cases. (1 <= T <= 100)

For each test case, the first line contains two space-seperated numbers n, m: n is the number of citizens in Mayapur and m denotes the number of unrepaired roads (1 <= n <= 10^5, 1 <= m <= min (n * (n - 1) / 2, 2 * 10^5)).

The next line contains n space-separated integers, which are either 0 or 1, denoting for successive citizens whether they are a milkman or not.

Then, for each of the next m lines, each line contains three space-seperated integers u, v and c, denoting that there exists a unrepaired road between u and v such that the cost of repairing of road is c. (1 <= u, v <= n and u != v, 1 <= c <= 10^9.) 

Output

For each test case output the cost as required.

Example

Input:
1
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
Output:
5

hide comments
rishi_07: 2017-03-12 16:16:14

Praveen Dhinwa _/\_

karthik_vg: 2017-02-14 16:21:45

one of the best question to learn disjoint sets find union

cjycjy: 2016-12-15 10:57:46

May be long long ↓

vivekkodu: 2016-09-25 12:00:28

Covered following cases, still getting WA
There is no milkmen in the city
Everyone is milkman
Some milkman is not connected to anyone
Some person is not connected to anyone
Multiple paths between 2 people
Milkmen and people are forming disjoint set

Any idea about missing edge case?

avisheksanvas: 2016-07-28 20:07:49

Great Problem :)

Liquid_Science: 2016-02-04 17:52:59

AC in 5 mins! now i have started to get the knack of it :)

Shubham Sinha: 2016-01-20 13:57:59

strong test cases !!!!

sarvagya: 2015-08-20 18:42:56

solve this question if you want quick points :P . It is too straight forward .

Rajat De: 2015-02-25 21:26:47

dont know why but AC with krushkal's and WA with prims

vishal: 2015-01-09 12:00:31

awesome prob.
google the problem go through hint in the editorial and use mst.


Added by:praveen123
Date:2014-02-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge