Minimum Cost to Connect Houses

You are given a network of houses and roads connecting them. Each road has an associated upgrade cost. Your task is to determine the minimum total cost required to upgrade a set of roads such that every house is reachable from every other house.

This problem is a classic Minimum Spanning Tree (MST) problem. One common approach to solve it is by using Kruskal's algorithm with the union-find (disjoint set union) data structure.

The cost of the upgraded road network is given by the sum of the costs of all roads chosen in the MST. The optimality of the MST is well-known and can be expressed by the formula in LaTeX:

$$\text{MST Cost} = \min_{T \subseteq E \text{ is a spanning tree}} \sum_{e \in T} \text{cost}(e). $$

Make sure to read the input from stdin and output the result to stdout.

inputFormat

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

The next M lines each contain three integers u, v, and c, indicating a road connecting house u and house v with an upgrade cost of c. It is guaranteed that the houses are numbered from 1 to N.

outputFormat

Output a single integer representing the minimum cost to upgrade the road network so that every house is connected.

## sample

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

7