404 - 最小生成树(MST)

通过次数

48

提交次数

147

时间限制 : 1 秒
内存限制 : 128 MB

最小生成树:Minimal Spanning Tree

给定结点数为n,边数为m的带权无向连通图G,所有结点编号为1,2,...,n

G的最小生成树的边权和。

输入

第一行输入两个整nm,表示点数和边数。

接下来m行,每行包含3个整数a,b,c,表示有一条a,b相连的边,花费为c的边。

输出

一个整数表示G的最小生成树的边权和。

样例

输入

7 12
1 2 9
1 5 2
1 6 3
2 3 5
2 6 7
3 4 6
3 7 3
4 5 6
4 7 2
5 6 3
5 7 6
6 7 1

输出

16

提示

数据规模

1≤n≤2*10^5,0≤m≤5*10^5,  边权值为int型整数