P10604 BZOJ4317 Atm's Tree.

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...

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.

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 $n$ lines. The $i$-th line indicates the $k$-th smallest distance starting from node $i$.

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