题目描述

特梅利亚是北方最强大的王国之一，首都是维吉玛城。住在维吉玛城的女术士特莉丝发现了强大的魔法异常，于是决定调查特梅利亚王国，寻找异常的源头。

特梅利亚有 $n$ 座城市，编号为 $1$ 到 $n$，首都维吉玛编号为 $1$。这些城市由 $n-1$ 条双向道路连接，第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，长度为 $w_i$。保证仅通过这些道路，可以从任意城市到达任意其他城市。

特莉丝计划从维吉玛出发，访问所有 $n$ 座城市，最后回到维吉玛。她可以沿道路步行，但这很慢。她还有 $k$ 个传送水晶，可以用来在城市之间瞬间移动。

在任意时刻，特莉丝可以把一个水晶留在当前所在城市。之后，她可以使用之前留下的某个水晶，瞬间沿最短路径返回到放置该水晶的城市。使用后，该水晶会被摧毁。特莉丝可以以任意顺序放置和使用水晶。

不过，传送会留下痕迹。具体来说，如果特莉丝在城市 $a$ 使用水晶并到达城市 $b$，那么从 $a$ 到 $b$ 的最短路径上的所有城市，包括 $a$ 和 $b$，都会留下魔法痕迹。之后，任何其他传送路线都不能经过已经留下魔法痕迹的城市。

请帮助特莉丝。对于每个 $j=1,2,\ldots,k$，求出在使用不超过 $j$ 个水晶的情况下，为了访问所有城市并回到维吉玛，特莉丝需要步行的最小总距离。

输入格式

第一行包含两个整数 $n,k$，分别表示城市数量和特莉丝拥有的传送水晶数量。

接下来 $n-1$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，长度为 $w_i$。

输出格式

输出 $k$ 个整数，其中第 $j$ 个数表示使用不超过 $j$ 个水晶时需要步行的最小距离。

这些整数可以用空格或换行分隔。

数据范围

• $2\le n\le 500000$；
• $1\le k\le n$；
• $1\le u_i,v_i\le n$；
• $1\le w_i\le 10^9$；
• 给出的图是一棵树。

子任务

记号「题面测试」表示该子任务还要求通过题面中的测试数据。

完全二叉树指由 $2^s-1$ 个点组成的树，即 $n=2^s-1$，并且对于每个 $i=1,2,\ldots,2^{s-1}-1$，都存在两条边 $(i,2i)$ 和 $(i,2i+1)$。

特殊图指由奇数个点组成的树，并且对于每个 $i=1,2,\ldots,\frac{n-1}{2}$，都存在两条边 $(1,2i)$ 和 $(2i,2i+1)$。

样例 1

输入

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

输出

6

样例 2

输入

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

输出

86
85

样例说明

样例 1 中，一个最优路线如下：特莉丝在城市 $1$ 放置水晶，然后沿路线

1 -> 2 -> 1 -> 3 -> 4 -> 3 -> 5

行走，最后使用水晶，瞬间回到城市 $1$。

样例 2 中，对于使用不超过 $1$ 个水晶的情况，可以沿路线

1 -> 5 -> 1

之后在城市 $1$ 放置水晶，再沿路线

1 -> 9 -> 1 -> 2 -> 3 -> 7 -> 3 -> 4 -> 8 -> 4 -> 6 -> 10

并使用城市 $1$ 的水晶，路线长度为 $86$。

对于使用不超过 $2$ 个水晶的情况，可以使用两个水晶 $x,y$：

• 在城市 $1$ 放置水晶 $x$；
• 沿路线 $1\to5\to1\to9\to1\to2\to3\to7\to3\to4\to6$ 行走；
• 在城市 $6$ 放置水晶 $y$；
• 走到城市 $10$，使用水晶 $y$ 返回城市 $6$；
• 再沿路线 $6\to4\to8$ 行走；
• 最后使用水晶 $x$ 结束行程。