配点 : 1200 点
問題文
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 均为整数
入力
输入是按以下格式从标准输入给出的。
N X
A_1 B_1 C_{1}
.
.
.
A_{N-1} B_{N-1} C_{N-1}
出力
答案 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