#202. 宝藏

宝藏

题目描述

有 n 个洞穴和若干候选通道,通道有长度。可任选初始洞穴,然后每次从已经到达的洞穴开通一条边到一个新洞穴,最终形成一棵树。若新洞穴在树中的深度为 d(根深度0),开通长度 L 的通道费用为 d×L。求到达所有洞穴的最小总费用。

输入格式

首行 n、m;随后 m 行 u、v、L 描述无向通道。

输出格式

输出最小总费用。

样例输入

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

样例输出

4

题意整理;原题与输入输出格式对照。