题目描述
给定结点数为 n,边数为 m 的带权无向连通图 G,所有结点编号为 1,2,⋯,n。
求 G 的最小生成树的边权和。
输入格式
第一行两个正整数 n,m。
之后的 m 行,每行三个正整数 ui,vi,wi(1≤ui,vi≤n,0≤wi≤109),描述一条连接结点 ui 和 vi,边权为 wi 的边。
输出格式
一个整数表示 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×105,0≤m≤5×105。