Water Supply In A Village

Posted: 2 Apr, 2021
Difficulty: Hard

PROBLEM STATEMENT

For Example:

``````For ‘N’ = 3, ‘WELLS[]’ = ‘[1,2,2]’, ‘PIPES[]’ = [ [1, 2, 1], [2 , 3, 1]]. The image shows the costs of connecting houses using pipes. The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.
``````

Ninja wants to find out the minimum total cost to supply water to all houses in the village. Can you help the Ninja to find out this minimum cost?

Input Format
``````The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case contains two integers ‘N’ and ‘K’ representing the number of Houses in the village and the size of ‘PIPES’ respectively.

The next line contains ‘N’ single space-separated integers denoting ‘WELLS[i]’.

The next ‘K’ line contains 3 single space-separated integers denoting ‘PIPES[i][0]’, ‘PIPES[i][1]’ and ‘PIPES[i][2]’.
``````
Output Format :
``````For each test case, print the minimum cost to supply water to all the houses in the village.

The output for each test case is printed in a separate line.
``````
Constraints :
``````1 <= T <= 100
1 <= N <= 10 ^ 2
0 <= WELLS[i] <= 10^5
1 <= K <= 10000
1 <= PIPES[i][0], PIPES[i][1] <= N
0 <= PIPES[i][2] <= 10^5
PIPES[i][0] != PIPES[i][1]

Where ‘T’ is the number of test cases, ‘N’ is the number of houses in the village, WELL[i]’ denotes the cost of inserting a well at house ‘i’ and ‘PIPES[i][0]’, ‘PIPES[i][1]’ and ‘PIPES[2]’ represents the cost to connect house ‘PIPES[i][0]’ to ‘PIPES[i][1]’.

Time Limit: 1 sec
``````