In country P, there are $n$ villages and $n-1$ bidirectional roads to be built. The $i$-th road connects $u_i$ and $v_i$ with a construction cost of $c_i$. It is guaranteed that any two villages can reach each other through some sequence of these roads.

The king and $k$ guards are initially at some village $r$. The $i$-th guard needs to reach a specific destination village $x_i$.

The king will choose a set of roads to build such that the total cost is minimized, while ensuring that each guard can travel from $r$ to their respective destination $x_i$ using only the built roads.

For each $r \in [1, n]$, calculate the maximum possible total cost of the roads the king must build, considering all possible choices of destinations $x_i \in [1, n]$ for the $k$ guards.

Input

The first line contains two positive integers $n$ and $k$.

The next $n-1$ lines each contain two positive integers $u_i, v_i$ and a non-negative integer $c_i$.

Output

Output $n$ lines. The $r$-th line should contain a non-negative integer representing the answer for that $r$.

Examples

Input 1

11 3
1 2 5
2 3 3
2 6 5
3 4 4
3 5 2
1 7 6
7 8 4
7 9 5
1 10 1
10 11 1

Output 1

28
28
28
32
30
32
28
32
32
29
30

Note 1

Graph visualization tool: https://csacademy.com/app/graph_editor/

For example, when $r=1$, if $x_1=4$, $x_2=6$, and $x_3=9$, the king needs to build roads with a total cost of $28$, and it can be proven that no configuration yields a higher cost.

Input 2

See the provided files; this sample satisfies the constraints of subtask 4.

Output 2

See the provided files.

Constraints

For all data, $1 \le k \le n \le 10^5$, $0 \le c_i \le 10^9$.