Problem Statement

There is a village with n houses connected by pipes. You need to ensure that each house will get a water supply.

For each house i, you can either dig a well inside it with cost wells[i - 1] or get water via a pipe from another well to it. The costs to get water via pipes between houses are given by the array pipes where each pipes[j] = [house1_j, house2_j, cost_j] represents the cost to connect house1_j and house2_j together using a pipe. Here, pipe connection is bidirectonal.

Return the minimum total cost to supply water to all houses.

Examples

Example 1:

• Input: n = 5, wells = [3, 2, 1, 4, 5], pipes = [[1, 2, 2], [2, 3, 3], [3, 4, 1], [4, 5, 2]]
• Output: 8
• Explanation: Dig wells for houses 3, and supply water to other houses from house 3.

Example 2:

• Input: n = 4, wells = [1, 2, 2, 3], pipes = [[1, 2, 1], [2, 3, 1], [3, 4, 1]]
• Expected Output: 4
• Explanation: Dig wells for houses 1, and lay pipes between houses 1 and 2, houses 2 and 3, and houses 3 and 4.

Example 3:

• Input: n = 3, wells = [2, 1, 2], pipes = [[1, 2, 2], [2, 3, 1]]
• Output: 4
• Explanation: Dig wells for houses 2, and lay a pipe between houses 2 and 3, and 1 and 2.

Constraints:

• 2 <= n <= 10⁴
• wells.length == n
• 0 <= wells[i] <= 10⁴
• 1 <= pipes.length <= 10⁴
• pipes[j].length == 3
• 1 <= house1_j, house2_j <= n
• 0 <= cost_j <= 10_j
• house1_j != house2_j

Try it yourself

Try solving this question here: