Problem Description

There is a country consisting of $ N $ cities and $ N-1 $ roads. Each city is numbered $1, 2, \ldots, N$. The $ i $th road ( $1 \leq i \leq N-1$ ) connects city $ A_i $ and city $ B_i $ with a length of $ C_i $. The roads can be traversed in both directions, and any two cities can travel to each other through some roads.

One day, for two cities $ i $ and $ j $ where $1 \leq i < j \leq N$, if there is no direct road connecting city $ i $ and city $ j $, a new road of length $ X $ is added to directly connect city $ i $ and city $ j $.

Let $ d(u, v) $ be the shortest distance from city $ u $ to city $ v $. For two cities $ i $ and $ j $ where $1 \leq i < j \leq N$, calculate $ d(i, j) $ and output the sum of these distances.

Input Format

The input is given from the standard input in the following format:

$ N $ $ X $ $ A_1 $ $ B_1 $ $ C_1 $ $\ldots$ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

51

Sample Input #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

Sample Output #2

11278

Notes/Hints

Constraints

• $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$
• Before the operation, any two cities can travel to each other through some roads.
• $ C_i $ and $ X $ are integers.

Sample Explanation 1

The following figure represents the relationship between cities and roads. The blue solid lines represent the original $ N-1 $ roads, and the black dashed lines represent the new roads of length $ 3 $ added by the operation.

见题面 Input 部分

见题面 Output 部分