Atm的树

时间限制:20s      空间限制:128MB

题目描述

Atm有一段时间在虐qtree的题目,于是,他满脑子都是tree,tree,tree……
于是,一天晚上他梦到自己被关在了一个有根树中,每条路径都有边权,一个神秘的声音告诉他,每个点到其他的点有一个距离(什么是距离不用说吧),他需要对于每个点回答:从这个点出发的第k小距离是多少;
如果atm不能回答出来,那么明天4019的闹钟将不会响,4019全寝可能就迟到了,所以atm希望你帮帮他。


输入格式

第一行,两个正整数n,k,表示树的点数,询问的是第几小距离;
第二~n行,每行三个正整数x,y,w,表示x和y之间有一条边,x为父亲,边权为w;


输出格式

n行, 每行一个数,第i行输出从i开始第k小距离


样例输入

5 2
1 5 2
1 2 4
2 3 6
2 4 5



样例输出

 4
 5
 10
 9
 6

提示

100% n<=15000, 边权在1~10之间,为了方便,保证1为根;K<=5000


题目来源

没有写明来源

Menuappsclose