Background

The problem is from the original BZOJ. We acknowledge that the statement and the original testdata are copyrighted by the original BZOJ or by the problem author who authorized BZOJ to use it. If you are the copyright owner and believe that your rights have been infringed, please contact us.

Atm spent some time working hard on problems about qtree, so his head was full of tree, tree, tree...

Problem Description

So, one night he dreamed that he was locked inside a rooted tree. Each path has edge weights. A mysterious voice told him that there is a distance from each node to other nodes. For each node, he needs to answer: what is the $k$-th smallest distance starting from this node?

If atm cannot answer it, then tomorrow the 4019 alarm clock will not ring, and the whole dorm 4019 may be late, so atm hopes you can help him.

Input Format

The first line contains two integers $n,k$, representing the number of nodes in the tree being queried, and the $k$ in the problem.

The next $n-1$ lines each contain three positive integers $u,v,w$, indicating that there is an edge with weight $w$ between node $u$ and node $v$.

Output Format

Output $n$ lines. The $i$-th line indicates the $k$-th smallest distance starting from node $i$.

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

4
5
10
9
6

Hint

For all data, $1\leq n\leq 15000$, $1\leq k\leq 5000$, $1\leq w\leq 10$. The root of the tree is node $1$.

Translated by ChatGPT 5