K-th Smallest Distance in a Weighted Tree

You are given a weighted tree with n nodes (numbered from 1 to n) where each edge has an associated positive weight. For each node, consider the distances from that node to every other node in the tree. The distance between two nodes is defined as the sum of the weights on the unique simple path connecting them. Your task is to determine, for every node, the k-th smallest distance among these distances. If a node does not have k distances (i.e. when k > n-1), output -1 for that node.

Note: All formulas must be represented in LaTeX format. For example, the parameter k should be shown as $k$ in the problem statement.

If the solution does not compute the correct answer for each node, tomorrow's 4019 alarm will not ring and everyone in the 4019 dormitory might be late!

inputFormat

The first line contains two integers n and k — the number of nodes in the tree and the parameter $k$, respectively.

Each of the following n - 1 lines contains three integers u, v, and w describing an edge between nodes u and v with weight w.

The tree is undirected and connected. Nodes are 1-indexed.

outputFormat

Output n lines. The i-th line should contain a single integer representing the $k$-th smallest distance from node i to any other node. If node i does not have $k$ distances (i.e. if $k > n - 1$), print -1 instead.

sample

3 1
1 2 1
2 3 2

1
1
2