Minimum Cost to Provide Water

You are given N houses and M possible water pipes connecting them. Each pipe connects two houses with a given cost. Your task is to determine the minimum total cost required to connect all the houses so that water can be provided to everyone. If it is impossible to connect all houses, output -1.

This problem can be solved using a Minimum Spanning Tree algorithm such as Kruskal's algorithm with union-find (disjoint set union) data structure. The input consists of the number of houses, number of pipes, and the details of each pipe. The output should be the minimum cost of connecting all houses or -1 if not all houses can be connected.

For a mathematically formal representation, if we consider the graph as \( G=(V,E) \) with \( |V|=N \) and each edge \( (u,v) \) having a weight \( c \), then we want to find a spanning tree \( T \subseteq E \) such that:

[ \min \sum_{(u,v) \in T} c(u,v) \quad \text{subject to} \quad T \text{ connects all vertices}. ]

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers N and M representing the number of houses and the number of pipes respectively.
• The next M lines each contain three integers u, v, and c describing a pipe that connects house u with house v at cost c.

outputFormat

Output a single integer, which is the minimum total cost to connect all houses. If it is impossible to connect all houses, output -1. The output is printed to standard output (stdout).

4 5
1 2 1
2 3 4
3 4 2
4 1 3
1 3 5

6