Minimum Cost Traversal

You are given a connected, undirected graph with n vertices and m edges. Each edge has a weight. Your task is to compute a minimum-cost traversal that visits all vertices at least once.

This problem is equivalent to finding a minimum spanning tree (MST) of the graph. The MST connects all vertices with the minimal possible total edge weight. You are allowed to start from any vertex.

The cost of the traversal is the sum of the weights of the MST. Use Prim's (or any other correct algorithm such as Kruskal's) algorithm to compute the MST.

Note: The input graph is guaranteed to be connected.

The formula for the MST cost in terms of its chosen edges is:

\( \text{MST} = \min \sum_{e \in E'} w(e), \quad \text{subject to } E' \text{ connects all vertices} \).

inputFormat

The first line of input contains two integers n and m, representing the number of vertices and edges respectively.

The following m lines each contain three integers u, v, and w where u and v are the endpoints of an edge and w is the weight of that edge.

You can assume that 1 ≤ u, v ≤ n and that the graph is connected.

outputFormat

Print a single integer representing the minimum total cost of traversing the graph (i.e., the sum of the weights in the minimum spanning tree).

## sample

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

6