给定一个N(2<=N<=150000)个节点N－1边的树，每条边有一个长度L（1<=L<=1000000）。
现在定义：
“路径(u,v)长度”表示顶点u到v之间的最短路径
“u的第k远路径”表示从顶点u出发的第k长路径。
请编写一个程序，计算这棵树中每个顶点的的第k远路径的长度。

输入第一行包含一个整数T（T<=50），表示测试数据的组数。
在每一组测试数据中，
第一行为两个整数N和K(1<=K<=20且K<=N-1)。
接下来的N-1行，每行包含三个整数u,v,L（0<=u,v<=N-1）,表示顶点u到v有一条边长度为L。

对于每组数据，输出一行，为N个整数（之间用一个空格隔开），其中第i(i=0,1,2,…,N-1)个整数表示顶点i的答案。

2
4 1
0 1 4
1 2 5
2 3 9
3 2
0 1 12
0 2 19

18 14 9 18
12 12 19