到 3031 年，ICPC 变得如此受欢迎，以至于必须建造一座全新的城镇来容纳所有的世界总决赛队伍。这座城镇设计精美，拥有完善的道路网络。不幸的是，在准备预算时，城镇规划者忘记考虑限速标志的成本。他们请求你帮助他们确定所需的最低额外资金。

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

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

安装一个限速标志的成本为 $c$ 美元。也可以通过改善道路的安全性和质量来提高其限速，这反过来可能会减少所需的限速标志数量。将一条道路的限速提高 $x$ km/h（双向）的成本为 $x$ 美元。为了避免投诉，市政委员会不允许降低任何已经分配的限速。

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

图 B.1：道路网络和限速示意图。

输入格式

输入的第一行包含两个整数 $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 \neq v$) 是道路两端的交叉路口，$s$ ($1 \le s \le 10^5$) 是该道路当前的限速（单位：km/h）。

输出格式

输出满足上述所有规则的升级道路和安装限速标志的最低总成本。

样例

样例输入 1

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

样例输出 1

7

样例输入 2

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

样例输出 2

9