問題文

N 個の都市と N-1 個の道からなる国があります。各都市には 1, \, 2, \, … \, , \, N と番号がついています。 i(1 ≦ i ≦ N-1) 番目の道は都市 A_i と都市 B_i を長さ C_i でつないでいます。 道は双方向に移動可能で、どの都市同士も何本かの道を通って互いに行き来することが可能です。

ある日、1≦i<j≦N を満たす 2 つの都市 i, \, j について都市 i と 都市 j を直接つなぐ道が存在しない場合、都市 i と 都市 j を直接つなぐ長さ X の道を追加する、という操作が行われました。

d(u, \, v) を都市 u から都市 v までの最短距離として、 1≦i<j≦N を満たす 2 つの都市 i, \, j について d(i, \, j) をそれぞれ求め、その総和を出力してください。

制約

• 2 ≦ N ≦ 10^{5}
• 1 ≦ A_i, \, B_i ≦ N(1 ≦ i ≦ N-1)
• 1 ≦ C_i ≦ 10^{5}(1 ≦ i ≦ N-1)
• 1 ≦ X ≦ 10^5
• 操作が行われる以前の時点において、どの 2 つの都市同士も何本かの道をたどって移動可能
• C_i, \, X はいずれも整数

入力例 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