给定一棵包含 $N$ 个顶点的树。顶点编号从 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$，权重为 $C_i$，其中 $1 \le i \le N - 1$。

树中两个顶点之间的“传送距离”定义为连接它们的最短路径上边的最大权重。顶点到自身的传送距离定义为 $0$。

居住在树上的人们想要举行 $N$ 次会议。第 $i$ 次会议由居住在编号为 $1$ 到 $i$ 的顶点上的人参加。今年，由于冠状病毒的传播，会议参与者将前往 $X$ 个选定的地点，然后从这些地点通过互联网连接。

更正式地说，对于每次会议，我们将选择 $X$ 个两两不同的顶点 $v_1, v_2, \dots, v_X$。一旦确定了这些顶点，每个人都会移动到 $v_1, \dots, v_X$ 中传送距离最小的那个顶点。我们将给定 $X$ 和 $i$ 下的“会议成本”定义为会议参与者中传送距离的最大值。我们将以使会议成本尽可能小的方式选择顶点 $v_1, \dots, v_X$。

$X$ 的值取决于冠状病毒的情况，可能在 $1$ 到 $K$ 之间变化。为了提前准备会议，请编写一个程序，对于 $N$ 次会议中的每一次，计算所有可能的 $X$ 值（从 $1$ 到 $K$）对应的会议成本之和。

输入格式

输入的第一行包含两个整数 $N$ 和 $K$：顶点数量和 $X$ 的上限（$1 \le K \le N \le 3 \cdot 10^5$）。

接下来的 $N - 1$ 行描述了这棵树。每行包含三个整数 $A_i, B_i$ 和 $C_i$，表示顶点 $A_i$ 和 $B_i$ 之间存在一条权重为 $C_i$ 的边（$1 \le A_i, B_i, C_i \le N$）。保证给定的图是一棵树。

输出格式

输出 $N$ 行。第 $i$ 行输出第 $i$ 次会议对于所有 $X$ 从 $1$ 到 $K$ 的会议成本之和。

样例

样例输入 1

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

样例输出 1

0
4
13
21
23
23
30
31
33
34

样例输入 2

8 3
7 3 4
4 5 2
3 6 1
6 8 6
8 5 1
2 5 8
1 5 2

样例输出 2

0
8
14
16
16
16
18
18