题目描述

给出 $1$ 棵 $N$ 个节点的树，每条边上有一条权值，对于所有不同的点对 $(u,v) \ (u<v)$ 之间的路径按长度进行排序。要求输出前 $M$ 长的路径长度。

输入格式

第一行有 $2$ 个整数 $N,M$，接下来 $N-1$ 行每行有 $3$ 个整数 $u,v,w \ (1\leq u,v \leq N, \ 0 \leq w \leq 32767)$ 代表了顶点 $u$ 和 $v$ 之间有一条长度为 $w$ 的边。

输出格式

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

4 3
1 2 0
2 3 4
2 4 5

9
5
5

提示

对于 $20\%$ 的数据，有 $N \leq 1000$。

对于 $50\%$ 的数据，有 $N \leq 10^4$。

对于 $100\%$ 的数据，有 $N \leq 5 \times 10^4, \ M \leq \min\left\{\dfrac{N \times (N-1)}{2},3 \times 10^5\right\}$。

题目来源

By abs