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

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

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