QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+4]

# 415. 最小生成树

统计

题目描述

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

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

输入格式

第一行两个正整数 n,m

之后的 m 行,每行三个正整数 ui,vi,wi1ui,vin0wi109),描述一条连接结点 uivi,边权为 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

子任务

1n2×1050m5×105