Kth Number I

给定一棵包含 $N$ 个节点的树，每条边都有一个非负权值。对于所有不同的点对 $(u,v)$，其中 $u<v$，将它们之间的路径长度按从大到小的顺序排列。请输出前 $M$ 长的路径长度。

输入格式

第一行包含两个整数 $N,M$。

接下来 $N-1$ 行，每行包含三个整数 $u,v,w$，表示节点 $u$ 与节点 $v$ 之间有一条长度为 $w$ 的边，其中 $1\le u,v\le N$，$0\le w\le 32767$。

输出格式

输出 $M$ 行，第 $i$ 行输出第 $i$ 长的路径长度。

样例输入

4 3

1 2 0

2 3 4

2 4 5

样例输出

9
5
5

数据范围

• 对于 $20\%$ 的数据，$N\le 10^3$；
• 对于 $50\%$ 的数据，$N\le 10^4$；
• 对于 $100\%$ 的数据，$N\le 5\times 10^4$，$M\le \min\left(\frac{N(N-1)}{2},3\times 10^5\right)$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

4 3

1 2 0

2 3 4

2 4 5

输出

9
5
5