在 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 1output
28
28
28
32
30
32
28
32
32
29
30explanation
图论可视化工具：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$。
| 子任务编号 | 特殊限制 | 分值 |
|---|---|---|
| $1$ | $n\le 18$ | $8$ |
| $2$ | $n\le 200$，$k\le 20$ | $11$ |
| $3$ | $n\le 1000$，$k\le 100$ | $17$ |
| $4$ | $n\le 2000$ | $20$ |
| $5$ | $k=1$ | $12$ |
| $6$ | $ $ | $32$ |
时间限制：$\texttt{1s}$
空间限制：$\texttt{512MB}$