Minimum Cost to Connect Houses

You are given n houses labeled from 1 to n and m pipes, where each pipe connects two different houses and has an associated cost. Your task is to compute the minimum total cost to connect all houses so that water can be supplied to every house. If it is not possible to connect all houses, output -1.

This problem can be solved using Kruskal's algorithm to find a Minimum Spanning Tree (MST). The total cost of the MST is given by:

$$\text{Total Cost} = \sum_{e \in MST} \text{cost}(e) $$

If there are fewer than n-1 edges in the MST, then it is impossible to connect all houses, and you should output -1.

inputFormat

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

n m
u1 v1 w1
u2 v2 w2
... 
um vm wm

Where:

• n is the number of houses.
• m is the number of pipes.
• Each of the next m lines contains three integers u, v and w representing a pipe connecting house u and house v with cost w.

outputFormat

Output a single integer to stdout: the minimum cost required to connect all houses, or -1 if it is impossible.

## sample

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

6