Description

到了 3031 年，ICPC 变得如此受欢迎，以至于需要建造一个全新的小镇来容纳所有的世界总决赛队伍。小镇设计得非常漂亮，配备了道路网络。不幸的是，在准备预算时，城镇规划者忘记考虑限速标志的成本。他们请你帮助他们确定所需的最小额外资金。

ICPC 的道路网络由连接两个交叉路口的道路组成。每条道路都是双向的，并且已经分配了一个速度限制，该限制对两个方向都有效。为了节省资金，使用了最少可能数量的道路。换句话说，从任何一个交叉路口到另一个交叉路口只有一条路线。

限速标志需要安装在任何驾驶员沿任何路线行驶时限速可能发生变化的所有地方。更准确地说，如果存在一个交叉路口，至少有两条道路的限速不同，那么从该交叉路口出发的所有道路都需要在该交叉路口安装限速标志。注意，有些道路可能需要在两端各安装一个限速标志。

安装一个限速标志的成本是 $c$ 美元。也可以提高任何道路的安全性和质量，以便可以提高其限速，这可能会减少所需的限速标志数量。将一条道路的限速提高 $x$ 公里/小时（在两个方向上）需要花费 $x$ 美元。为了避免投诉，市议会不允许降低任何已经分配的限速。

图 B.1 展示了样例输入 1 和样例输入 2 中给出的情况。

Input Format

输入的第一行包含两个整数 $n$ 和 $c$，其中 $n$ ($1 \le n \le 20,000$) 是交叉路口的数量，$c$ ($1 \le c \le 10^5$) 是安装一个标志的成本。接下来的 $n-1$ 行中的每一行包含三个整数 $u$，$v$ 和 $s$，其中 $u$ 和 $v$ ($1 \le u, v \le n; u e v$) 是道路两端的交叉路口，$s$ ($1 \le s \le 10^5$) 是该道路当前的限速（以公里/小时为单位）。

Output Format

输出升级道路和安装限速标志的最低成本，以使城镇计划满足上述所有规则。

5 2
1 2 10
1 3 5
1 4 7
2 5 9

7

5 100
1 2 10
1 3 5
1 4 7
2 5 9

9

Hint

题面翻译由 ChatGPT-4o 提供。