题目背景

译自 9th Romanian Master of Informatics, RMI 2021 D2T2。$\texttt{0.3s,0.5G}$。

题目描述

橘猫有一棵树 $T=(V,E)$，边有边权。其中 $|V|=n$。

令 $\operatorname{path}(u,v)$ 为 $u,v$ 间最短路径上的边集。

对于根节点 $\mathrm{root}$，定义点集 $V'\subseteq V$ 的路径并为 $\displaystyle E'(V')=\bigcup_{u\in V'} \operatorname{path}(\mathrm{root},u)$。在此基础上，定义 $V'$ 的权值为 $\displaystyle \sum_{(u,v,w)\in E'(V') } w$，即路径并的边权和。

给定正整数 $k$。定义 $f(u)$ 为：当 $u$ 为根时，在 ${n\choose k}$ 种选择 $V'\subseteq V$ 且 $|V'|=k$ 的方案中，$V'$ 权值的最大值。

对于 $u=1,2,\cdots,n$，橘猫请你帮她求出 $f(u)$ 的值。

输入格式

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

接下来 $(n-1)$ 行，每行三个整数 $u,v,w$，表示 $(u,v,w)\in E$。

输出格式

输出 $n$ 行，第 $i$ 行一个整数表示 $f(i)$。

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

28
28
28
32
30
32
28
32
32
29
30

提示

样例解释

$u=1$ 时，一种最优方案是选择 $V'=\{4,6,9\}$。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le k\le n\le 10^5$；
• $0\le w\le 10^9$。