题目描述

给定一个 $n$ 个结点的树，结点用正整数 $1 \sim n$ 编号。每条边有一个正整数权值。用 $d(a, b)$ 表示从结点 $a$ 到结点 $b$ 路边上经过边的权值。其中要求 $a < b$。将这 $\frac{n \times (n-1)}{2}$ 个距离从大到小排序，输出前 $m$ 个距离值。

输入格式

第一行两个正整数 $n, m$。

下面 $n-1$ 行，每行三个正整数 $a, b, c$ 表示结点 $a$ 到结点 $b$ 有一条权值为 $c$ 的边。

输出格式

共 $m$ 行，如题所述。

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

7 
7 
6 
5 
4 
4 
3 
3 
2 
1

提示

对于 $100\%$ 的数据，$n \leq 5 \times 10^4$，$m \leq \min(3 \times 10^5, \frac{n \times (n-1)}{2})$，$a, b \leq n$，$C \leq 10^4$。