Minimum Repair Cost

You are given a connected undirected graph with n intersections and m roads. Each road has a repair cost associated with it. Your task is to repair some roads such that all intersections become connected and the total repair cost is minimized.

This problem is equivalent to finding the Minimum Spanning Tree (MST) of the graph. Recall that an MST of a connected graph with n vertices has exactly n-1 edges and minimizes the sum of the weights of the selected edges. The MST weight is given by:

$$ \text{MST cost} = \sum_{i=1}^{n-1} w_i $$

where \(w_i\) is the weight of the \(i^\text{th}\) edge in the MST.

Note: It is guaranteed that the input graph is connected (i.e. it is possible to reach any intersection from any other intersection).

inputFormat

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

The first line contains two integers n and m, where n is the number of intersections and m is the number of roads.

Each of the next m lines contains three integers u, v, and w representing a road between intersections u and v with repair cost w.

outputFormat

Output a single integer to standard output (stdout) — the minimum total repair cost required to connect all the intersections.## sample

4 5
1 2 3
2 3 4
3 4 5
1 4 9
1 3 7

12