14731473 SUSTech Online Judge
Problem 1473 --Minimum Cost

1473: Minimum Cost

Time Limit: 2 Sec  Memory Limit: 1024 MB
Submit: 1201  Solved: 230
[Submit][Status][Web Board]


There are n cities, m bidirectional roads connect to these n cities, each road has a cost. These m roads ensure that n cities connect to each other. 

Please find out the minimum cost to connect these n cities.


The first line contains two integers n, m \((1\leq n \leq 10^5, 1\leq m \leq 5*10^5)\), indicating there are n cities and m roads.

The next m lines, each line contains three integers u, v, w \((1\leq u, v \leq n, 1\leq w\leq 10^9)\), indicating that there is a road between u and v, cost w. 


Please output the minimum cost to connect these n cities.

Sample Input

4 4
1 2 1
2 3 1
3 4 2
1 4 8

Sample Output