King's Highway Connection

The Kingdom of Taco plans to connect all its cities using the King's Network. The goal is to select a subset of roads that connects all the cities with the minimal total cost. Each road connects two cities and has an associated cost. In other words, you need to find a Minimum Spanning Tree (MST) of the graph formed by the cities and roads.

The MST cost is defined as:

$$\text{MST cost} = \sum_{e \in T} w(e)$$

Here, \(T\) is the set of edges selected and \(w(e)\) is the cost of each edge.

You are guaranteed that the graph is connected, so it is always possible to connect all cities.

inputFormat

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

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

where:

• n (1 ≤ n ≤ 10⁵) is the number of cities.
• m (1 ≤ m ≤ 10⁵) is the number of roads.
• Each of the next m lines contains three integers u, v and w (1 ≤ u,v ≤ n, 1 ≤ w ≤ 10⁹), representing a road connecting city u and city v with a cost w.

outputFormat

Output a single integer to stdout — the minimal total cost to connect all the cities.

## sample

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

7