XiYangYang is a kind of lovely and rare sheep. They live in a peaceful land which can be described as a tree with N cities (nodes).

Now you have K robots. They will start at a same point and travel each edge at least once so that all XiYangYang will be caught. All your robots can stop at any city in the land. Because of expensive oil, you want minimize the total distance that your robots walk.

Input

First line : N K (N <= 15000, K <= 30)

Next N-1 lines: a b c (city a and city b are connected with a road whose length is c (1 <= a, b <= N, 0 <= c <= 100)

Output

N lines: The total distance that your robots walk if they all start at city i.

Example

Input:
5 3
1 2 7
2 3 5
3 4 14
3 5 8

Output:
42
39
34
42
42

Hint: my solution can get AC in 0.75~1 second.