给定一棵包含 $N$ 个顶点的树 $T$，每条边都有一个正整数权值。

你可以对给定的树执行以下操作：

• 从图中删除一条边，然后添加一条连接任意两个不同顶点的新边。新边的权值必须与被删除边的权值相同。所得的图不一定是一棵树。

我们将路径的权值定义为路径上所有边权之和。两个顶点 $u$ 和 $v$ 之间的距离定义为从 $u$ 到 $v$ 的最短路径（即权值最小的路径）的权值。如果不存在这样的路径，则定义距离为 0。

图的权值定义为任意两个顶点之间距离的最大值。

你的任务是求出在执行操作恰好 $i$ 次后，所能得到的图的最大权值，其中 $i = 0, 1, \dots, K$。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $K$。

接下来的 $N - 1$ 行中，第 $i$ 行包含三个空格分隔的整数 $u_i, v_i$ 和 $w_i$，表示一条连接两个不同顶点 $u_i$ 和 $v_i$ 的无向边，其权值为 $w_i$。

保证给定的边构成一棵树。

• $2 \le N \le 2000$
• $0 \le K \le 2000$
• $1 \le u_i < v_i \le N$ ($1 \le i \le N - 1$)
• $1 \le w_i \le 10^9$ ($1 \le i \le N - 1$)

输出格式

输出 $K + 1$ 个空格分隔的整数。第 $i$ 个整数应等于执行操作恰好 $i - 1$ 次后所能得到的图的最大权值。

样例

样例输入 1

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

样例输出 1

14 16

样例输入 2

7 2
1 2 4
2 3 6
2 4 2
4 5 5
2 6 1
4 7 3

样例输出 2

13 20 21