Minimum Construction Cost to Connect Houses

You are given a set of houses and a list of possible pipe connections between them. Each connection between two houses comes with a construction cost. Your task is to determine the minimum cost required to connect all houses together. If it is impossible to connect every house, output -1.

This problem is a classic Minimum Spanning Tree (MST) problem, which can be efficiently solved using Kruskal's algorithm in conjunction with the union-find (disjoint set) data structure.

The cost of connecting house i and house j is provided along with the pipe cost in the input. Optimize the overall cost while ensuring all houses are connected.

Hint: Use union-find with path compression and union by rank to efficiently manage the connected components.

inputFormat

The first line of input contains two integers, N and M, where N is the number of houses and M is the number of possible connections.

Each of the following M lines contains three integers: a, b, and c, representing a connection between house a and house b with the construction cost c.

outputFormat

Output a single integer which is the minimum total construction cost to connect all houses. If it is impossible to connect all houses, output -1.

## sample

4 5
1 2 10
1 3 15
2 3 5
2 4 20
3 4 10

25

</p>