题目描述

到了 3031 年，ICPC 变得十分受欢迎，以至于为了让所有参加世界总决赛的队伍有住的地方而修了一个小镇。这个小镇规划得很好，实现了一个路网。不幸的是，当制定预算时，这个小镇的规划者忘了把制作限速标志的花费考虑进来了。他们要求你帮他们确定最少需要追加多少资金。

ICPC 路网由道路组成，每条道路连接两个路口。每条道路都可以双向通行，并且都已经确定了限速，限速对双向通行的车辆均有效。为了节约资金，只有最少条数的道路可用。也就是说，从任意一个路口到任意另一个路口只有恰好一条路径。

对于沿任意路径行驶的任意司机，限速标志需要安装在限速可能变化的所有位置。更确切地说，如果存在一个路口，与这个路口相接的道路有至少两条限速不同，那么与这个路口相接的所有道路都需要在这个路口处安装限速标志。注意一些道路可能需要两个限速标志，一端安装一个。

安装一个限速标志需要花费 $c$ 美刀。当然，也可以改建任意一条道路，提升它的安全性和质量，这样的话，这条道路的限速会提高，需要安装的限速标志也会变少。对于一条道路，提升 $x$ 公里每小时的限速（对于双向都提升） 需要花费 $x$ 美刀。为了避免抱怨，镇议会不允许降低已有道路的限速。

输入格式

输入第一行包含两个整数 $n\ (1\le n\le 20\ 000)$ 和 $c\ (1\le c\le 10^5)$，$n$ 表示路口数，$c$ 表示安装一个限速标志的花费。

接下来 $n-1$ 行，每行三个整数 $u,v,s\ (1\le u,v\le n,u\neq v,1\le s\le 10^5)$。其中 $u$ 和 $v$ 表示一条道路两端的路口，$s$ 表示当前道路的限速为 $s$ 公里每小时。

输出格式

输出升级道路和安装限速标志，以满足以上条件的最小花费。

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