暂无测试数据。

题目描述

在奇怪的世界里，一棵拥有 $n$ 个节点的蒜头树骄傲地屹立着，每个连接节点的边都赋予了特定的权值。

每个节点上都生长着一颗蒜头，我们称之为蒜头君。节点 $i$ 上蒜头君的美丽度被定义为：

$B(i) = \sum\limits_{\text{cnt}(i,j)\le k}\text{dis}(i,j)$

这里，$k$ 是一个预设的常数，$\text{cnt}(i,j)$ 是节点 $i$ 到节点 $j$ 的路径中经过的边的数量，而 $\text{dis}(i,j)$ 是从节点 $i$ 到节点 $j$ 的路径中经过的所有边的权值之和。

请你计算出 $1\sim n$ 每个节点上蒜头君的美丽度。

输入格式

第一行，两个正整数，$n$ 和 $k$。 接下来 $n-1$ 行描述蒜头树,每行三个正整数 $u,v$ 和 $w$，表示 $u$ 和 $v$ 之间连了一条权值为 $w$ 的边。

输出格式

一行，$n$ 个数 $1 \sim n$ 每个节上蒜头君的美丽度，用空格隔开。

数据范围

对于 $20\%$ 的数据，树是一条链,边权 $ \leq 1000000000$

对于另外 $30\%$ 的数据，$n \leq 5000,k \leq 10$, 边权 $\leq 1000000000$

对于另外 $20\%$ 的数据，是一张菊花图

对于 $100\%$ 的数据，$n \leq 300000,k \leq 20$, 边权 $\leq 1000000000$

数据全部为随机生成

5 3
1 2 1
2 3 2
2 4 3
4 5 4

16 13 19 16 28