L. MST
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ nodes and $$$m$$$ edges. You want to select some subset of the edges such that it forms an undirected acyclic graph with the minimum possible sum of edge weights.

Print out the minimum possible sum of edge weights.

Input

The first line of input contains $$$n$$$ and $$$m$$$ $$$(1\le n,m\le 2\cdot 10^5)$$$ — the number of nodes and the number of edges, respectively.

The $$$j$$$th of the next $$$m$$$ lines contains 3 integers $$$u_j$$$, $$$v_j$$$, $$$w_j$$$ $$$(1\le u_j, v_j\le n, 1\le w_j\le 10^9)$$$ — the start node, end node, and weight of the $$$j$$$th undirected edge, respectively.

Output

Output a single integer, the minimum possible sum of edge weights of any valid set of edges.

Note

Sorry, we don't have the budget for samples.