橘猫发现了一棵树（一个无向连通无环图），树有 $N$ 个顶点，编号从 $1$ 到 $N$。在连接顶点 $x_i$ 和 $y_i$ 的每条边 $i$ ($1 \le i < N$) 上，有 $c_i$ 个特殊的猫零食。

橘猫可以选择恰好 $K$ 个顶点，从树的根节点出发，沿着通往所选顶点的路径行走，并获取这些路径上的所有猫零食。当然，每条边上的零食只能获取一次。由于橘猫很好奇，它想知道，如果分别以每个顶点 $i$（$1 \le i \le N$）作为树的根，通过最优地选择 $K$ 个顶点，它最多能获取多少个零食。

输入格式

输入的第一行包含两个整数 $N$ 和 $K$，分别表示树的顶点数和橘猫将要选择的顶点数。接下来的 $N-1$ 行，每行包含三个整数 $x_i, y_i$ 和 $c_i$，描述树的边。

输出格式

对于 $1 \le i \le N$，在第 $i$ 行输出如果以顶点 $i$ 为根时，橘猫能够获取的零食的最大数量。

数据范围

• $1 \le K \le N \le 100\,000$
• $0 \le c_i \le 1\,000\,000\,000$，对于 $1 \le i < N$

样例

输入 1

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

输出 1

28
28
28
32
30
32
28
32
32
29
30

说明

如果根节点是顶点 $1$，那么橘猫可以选择顶点 $4, 6$ 和 $9$。从根节点到所选顶点的路径分别为 $1-2-3-4$、$1-2-6$、$1-7-9$，这些路径上的零食总数为 $5 + 3 + 4 + 5 + 6 + 5 = 28$。注意，边 $1-2$ 上的零食只被计算了一次。