树上的路径

时间限制:10s      空间限制:256MB

题目描述

给定一个N个结点的树,结点用正整数1..N编号。每条边有一个正整数权值。用d(a,b)表示从结点a到结点b路边上经过边的权值。其中要求a<b.将这n*(n-1)/2个距离从大到小排序,输出前M个距离值。


输入格式

第一行两个正整数N,M
下面N-1行,每行三个正整数a,b,c(a,b<=N,C<=10000)。表示结点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 


提示

N<=50000,M<=Min(300000,n*(n-1) /2 )


题目来源

没有写明来源