E--最小生成树

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给出一个带权无向图,求出其最小生成树。保证图连通。

Input

对于每组数据:
第一行输入n,m。表示此图有n(n <= 50000)个点,m(m <= 200000)条边。
接下来m行,每行u,v,w。表示u,v之间有一条权值为w的边。

Output

 对于每组数据,输出一个整数代表对应的最小生成树的权值和。

Sample Input

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

Sample Output

2

Hint

 

Source

zmx