问题描述

有一个由 $N$ 个城市和 $N-1$ 条道路构成的国家。每个城市被编号为 $1, \\, 2, \\, \ldots , \\, N$。第 $i(1 \leq i \leq N-1)$ 条道路连接了城市 $A_i$ 和城市 $B_i$，长度为 $C_i$。道路是双向的，任意两个城市之间都可以通过多条道路来回移动。

有一天，如果不存在直接连接城市 $i$ 和城市 $j$ 的道路（其中 $1 \leq i<j \leq N$），则会进行以下操作：添加一条长度为 $X$ 的道路，直接连接城市 $i$ 和城市 $j$。

对于满足 $1 \leq i<j \leq N$ 的任意两个城市 $i$ 和 $j$，定义 $d(u, \\, v)$ 为从城市 $u$ 到城市 $v$ 的最短距离。请计算所有 $d(i, \\, j)$ 的和并输出。

约束条件

• $2 \leq N \leq 10^{5}$
• $1 \leq A_i, \\, B_i \leq N(1 \leq i \leq N-1)$
• $1 \leq C_i \leq 10^{5}(1 \leq i \leq N-1)$
• $1 \leq X \leq 10^5$
• 在进行操作之前的任意时刻，任意两个城市之间都可以通过多条道路来回移动
• $C_i, \\, X$ 均为整数

输入

从标准输入中按以下格式输入。

$N$ $X$ $A_1$ $B_1$ $C_{1}$ . . . $A_{N-1}$ $B_{N-1}$ $C_{N-1}$

输出

将答案输出在一行中。

示例 1

6 3
1 2 2
2 3 3
4 1 4
6 4 10
5 4 8

输出示例 1

51

下图表示了城市和道路之间的关系。蓝色实线表示原本存在的 $N-1$ 条道路，黑色虚线表示经过操作后新增的长度为 $3$ 的道路。

示例 2

20 68
12 10 34
12 14 35
12 9 15
17 9 37
1 17 47
1 2 12
11 2 7
11 15 32
13 11 15
13 4 2
5 1 35
20 5 51
3 4 39
16 11 21
3 18 70
17 8 68
20 7 2
6 3 34
19 2 5

输出示例 2

11278