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 bi-directoinal 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).


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.) 


For each test case output the cost as required.


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

hide comments
chetan4060: 2018-01-27 14:25:43

AC in one go:-)

codefield: 2018-01-19 21:57:55

kruskal rocks as usual

Last edit: 2018-01-19 22:00:18
sahil_1994: 2017-11-02 23:12:34

is the city connected or not ??

code_aim: 2017-10-23 07:02:08

Good question with tricky test case!!

babur: 2017-06-27 09:28:00

Its a classic Prim's algorithm question...

sas1905: 2017-06-12 05:37:54

Strong and tricky test cases..!!

akt_1998: 2017-06-11 22:48:36

prims ;)

siddharth_0196: 2017-03-25 20:13:32


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

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