IITWPC4I  Petya and Repairment of Roads
Petya live in a city named Mayapur. As the in the morning, everybody likes to drink hot tea in bed. So the citizens needs milk to produce tea. For this purpose, they want that they should be able to go to atleast some milkmen using bidirectoinal roads. There are m roads in the city but all of them are currently unrepaired, hence not a state of use.
As Petya cares about his city a lot. He got a project about reparing these roads. So he has to select some roads to repair such that every citizen is connected to atleast one milkman. For reparing each road he needs to pay a cost. As he does not want to spend a lot of money in it, He wants to minimize the cost needed in this project. Note that a milkmen does not need to go to some other milkmen for milk as he can take milk from his own home.
Help Petya in finding out minimum cost needed to repair the roads in the above given way. If it is not possible for a citizen to connect to any of the milkmen, output "impossible" (without quotes).
Input
First line contains T : number of test cases. (1 <= T <= 100)
For each test case, First line contains two space seperated number n, m: number of citizens in Mayapur and m denotes number of unrepaired roads.
Next line contains n space integers either 0 or 1 which indices that citizen is milkmen or not[1 means he is a milkman]. (1 <= n <= 10^5)
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 cost of repairing of road is c. (1 <= u, v <= n and u != v)
(1 <= m <= min (n * (n  1) / 2, 2 * 10^5). 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
chetan4060:
20180127 14:25:43
AC in one go:) 

codefield:
20180119 21:57:55
kruskal rocks as usual


sahil_1994:
20171102 23:12:34
is the city connected or not ??


code_aim:
20171023 07:02:08
Good question with tricky test case!! 

babur:
20170627 09:28:00
Its a classic Prim's algorithm question... 

sas1905:
20170612 05:37:54
Strong and tricky test cases..!! 

akt_1998:
20170611 22:48:36
prims ;) 

siddharth_0196:
20170325 20:13:32
DSU! :D 

rishi_07:
20170312 16:16:14
Praveen Dhinwa _/\_ 

karthik_vg:
20170214 16:21:45
one of the best question to learn disjoint sets find union 
Added by:  praveen123 
Date:  20140203 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  IITK ACA CSE online judge 