#1047. 2051. A Problem For Fun

2051. A Problem For Fun

#2051. A Problem For Fun

题目描述

给出一个N个结点的树,每条边有一个正整数权值,定义两个结点的距离为连接这两个结点路径上边权的和。对于每个结点i,它到其他N-1个结点都有一个距离,将这些距离从小到大排序,输出第K个距离。

输入格式

输入文件总共N行。第一行有两个正整数N和K。下面N-1行每行描述树的一条边(保证这些边可以构成一棵树),每行三个正整数u、v、w,表示从结点u到结点v有一条权值为w的边。 输入文件保证:N <= 50000, K < N, u <= N, v <= N, w <= 10000。

输出格式

输出文件总共N行,每行一个正整数,第i行的数对于结点i的答案。

样例

样例输入

6 3  

1 2 2  

1 3 4  

1 4 3  

3 5 1  

3 6 2  

样例输出

4  

6  

4  

7  

5  

6  

数据范围与提示