【MST最小生成树模板】小朋友开车

【MST最小生成树模板】小朋友开车

题目描述

小朋友在开车,他要从第一个点出发到所有的点,其中,有好多条路连接好多个地方,这些路并不是单行线,也就是说,小朋友可以从 xx 地开往 yy 地,那么他也可以从 yy 地开往 xx 地,现在小朋友想知道:这些路的距离之和最小是多少?

输入格式

第一行有两个正整数 n,mn,m 表示一共有 nn 个点,mm 条路。

接下来 mm 每行 3 个正整数 x,y,zx,y,z,表示在 xx 地和 yy 地之间,有一条长度为 zz 的路。

输出格式

输出第一行有一个整数,表示最终距离。

样例输入

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

样例输出

提示/说明

1n1021 \leq n\leq 10^21m2×1051 \leq m \leq 2 \times 10^5z104z \leq 10^4

保证所有路联通。

信息

ID
1002
难度
7
分类
生成树 点击显示
标签
递交数
22
已通过
1
通过率
5%
上传者