题目描述

给定一个 $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 \le 5 \times 10^4$，$m \le \min(3\times 10^5,\frac{n \times (n-1)}{2})$，$a,b \le n$，$C \le 10^4$。