描述

给出N个点M条边的无向联通图
求最小生成树大小

输入

第一行两个正整数N,M
接下来M行，一行三个整数
a,b,v表示a与b之间有一条权值为v的边

输出

一行一个整数，为最小生成树大小(边权和)

样例

输入

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

输出

12

范围

50% N<=1000 M<=3000
80% N<=\(10^4\) M<=\(10^5\)
90% N<=\(10^5\) M<=\(10^6\)
100% N<=\(10^6\) M<=\(3\ast 10^6\)

限制

5s
512M