本文共333个字,预计阅读时间需要1分钟。

Description

假期到了,xab出去兼职修路,现在有n个地点,编号为1-n,给定了m条道路要修,并给定你修这些道路所需费用,要使得任意两个地方都相通,要你求出这个最小的费用

Input

第一行两个正整数n ( 1 <= n <= 2 * 10^5 ) , m ( 0 <= m <= 5 * 10^5 ) 。

之后的m行,每行三个正整数 u ( 1 <= u <= n ) , v(1 <= v <= n ) , w ( 0 <= w <= 10 ^9 ),表示修u到v的路需要费用为w元。

Output

最小费用

Sample Input 1 

Sample Output 1