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 bidirectional 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 spaceseperated 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 spaceseparated 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 spaceseperated 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
vineetjai:
20200804 09:10:58
Ignoring "impossible" cost me 2 WA. 

sakshamdrose:
20200623 16:16:57
multisource prim's algo 

atharvat77:
20200610 04:14:07
In java using array to store edges and sorting them gave TLE while using priority queue it gets an AC Last edit: 20200610 04:26:10 

kaiecillius:
20200522 09:49:01
Can also be solved by Dijkstra's algo 

vinty:
20200418 21:08:10
Please note: If citizen is a milkman then value is 1 else it is zero. 

aryan12:
20200305 16:34:25
A very good question for people who want to implement Kruskal's. Don't know about Prims (lol) and not reading the question costed me 2WA. 

prateekpandey:
20200128 06:41:37
everyone is milkman:):)


y17prashant:
20191127 17:02:55
Make arrays till 3*10^5 .....costed me several RTE .... Nice problem ......


gauss14:
20191014 16:29:32
there can be multiple roads b/w 2 cities. 

pr4shan7:
20190628 15:24:42
DSU; do not connect already connected nodes! 
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 