33OJ
登录 注册

#A0088. 建设道路

建设道路

题目描述

一个村装有 nn 个房子,可以建 mm 条道路,每条道路连接这两个房子,修建这条道路需要 xx 元钱,现在需要你帮助设计一个方法,每两个房子之间都能互相到达并花费最少的价格。

输入格式

第一行两个数 nn , mm。 接下来 mm 行,每行三个整数,u,v,wu,v,w ,表示这个道路的价格

输出格式

一行一个数,为最少花费的价格。

5 10
2 4 3
5 1 16
3 5 4
2 2 15
5 4 6
1 3 15
5 1 5
1 4 1
2 3 1
1 4 20
29

数据规模与约定

对于 100%100\% 的数据,0≤n,m≤1050 \le n,m \le 10^5。 对于 100%100\% 的数据,0≤w≤1050 \le w \le 10^5。