在 P 国有 $n$ 个村子，以及 $n-1$ 条待修建的双向公路，第 $i$ 条公路连接 $u_i,v_i$，修建的代价为 $c_i$，保证任意两个村子可以通过一些双向公路互相到达。

已知国王和 $k$ 个守卫在某个村子 $r$，第 $i$ 个守卫需要到达某个村子 $x_i$。

国王会选择代价之和尽可能少的一些公路进行修建，使得每个守卫可以从 $r$ 出发经过这些公路到达目的地。

对于每个 $r\in[1,n]$，求在所有选择 $x_i\in[1,n]$ 的情况下，国王修建公路所需代价之和的最大值。

输入格式

第一行，两个正整数 $n,k$。

之后 $n-1$ 行，每行两个正整数 $u_i,v_i$ 和一个非负整数 $c_i$。

输出格式

共 $n$ 行，第 $r$ 行一个非负整数，表示对应的答案。

样例一

input

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

output

28
28
28
32
30
32
28
32
32
29
30

explanation

图论可视化工具：https://csacademy.com/app/graph_editor/

例如对于 $r=1$ 的情况，当 $x_1=4$，$x_2=6$，$x_3=9$ 时国王需要修建代价之和为 $28$ 的公路，且可以证明不会有代价更大的情况。

样例二

见下发文件，该样例符合子任务 $4$ 的限制。

数据范围与提示

对于所有数据，$1\le k\le n\le 10^5$，$0\le c_i\le 10^9$。

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$