Water Supply Optimization Problem

Given N houses in a village, determine the minimum cost to supply water to all houses either by building wells in the houses or by connecting them with pipes.

Explanation:

For each house i, you can build a well directly with a cost specified in the array WELLS[i]. Alternatively, you can connect two houses HOUSE1 and HOUSE2 using a pipe with a cost given in the array PIPES[i] = [HOUSE1, HOUSE2, COST]. Connections are bidirectional.

Input:

The first line of input contains an integer 'T' representing the number of test cases.
For each test case:
- The first line contains two integers ‘N’ and ‘K’ indicating the number of houses and the number of pipes respectively.
- The next line contains N space-separated integers denoting the cost of wells WELLS[i] for each house.
- The following K lines each contain three space-separated integers PIPES[i][0], PIPES[i][1], and PIPES[i][2] indicating the two houses to connect and the cost of connecting them.

Output:

For each test case, output the minimum total cost needed to supply water to all houses, each on a new line.

Example:

Input:
2
3 2
1 2 2
1 2 1
2 3 1
4 4
3 2 1 4
1 2 5
1 3 3
2 4 4
3 4 2
Output:
3
7

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]

Determine the optimal cost for each test case under the given constraints.