A village has n houses 0 .. n-1 that all need water. House i can dig its own well for
dig[i]. Alternatively, water can be shared through pipes: pipes[i] = [u, v, cost] lays an
undirected pipe between houses u and v for cost. A house has water if it has a well or is
connected by pipes to a house with a well.
Return the minimum total cost so that every house has water.
Examples
Input: dig = [5, 4, 6], pipes = [[0,1,1],[1,2,2]]
Output: 7
Explanation: dig at house 1 (4), pipe 0-1 (1) and 1-2 (2).
Input: dig = [1, 1, 1], pipes = [[0,1,5]]
Output: 3
Explanation: three cheap wells beat any pipe.
Constraints
1 <= n <= 10**4,0 <= len(pipes) <= 2 * 10**4,0 <= dig[i], cost <= 10**5- Target
O((n + E) log(n + E))time.
Goals
- Turn a per-node cost into edges from an extra virtual node
- Run a standard MST algorithm on the enlarged graph
- Recognise when a modelling trick removes a special case