首页 > 试题广场 >

最小生成树

[编程题]最小生成树
  • 热度指数:791 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解

一个有n户人家的村庄,有m条路连接着。村里现在要修路,每条路都有一个代价,现在请你帮忙计算下,最少需要花费多少的代价,就能让这n户人家连接起来。


输入描述:
输入第一行,两个整数n,m;
接下来m行,每行三个整数a,b,c,表示有路连接编号为a和b的人家,修路要花费的代价为c。
数据保证能将每户人家都连接起来。
注意重边的情况。,边权


输出描述:
输出最小的花费代价使得这n户人家连接起来。
示例1

输入

3 3
1 3 3
1 2 1
2 3 1

输出

2