题目描述

《数据规模》

【最小生成森林 Kruskal算法】 如题，给出一个无向图，求出最小生成森林的边权和。

输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。 接下来 M 行每行包含三个整数 Xi,Yi,Zi，表示有一条长度为 Zi 的无向边连接结点 Xi,Yi。

输出格式

输出一个整数表示最小生成森林的各边的长度之和。

样例

输入样例 1

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

输出样例 1

1 7

输入样例 2

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

输出样例 2

1 7

输入样例 3

7 8
1 3 2
1 2 4
3 2 2
3 4 3
2 4 3
5 7 2
5 6 3
6 7 3

输出样例 3

2 12