Paths

Time limit: 0.75s Memory limit: 512MB Input: Output:

Orange the Cat found a tree (an undirected connected acyclic graph) with NN vertices numbered from 11 to NN. On each edge i (1i<N)i \ (1 \leq i < N) connecting vertices xix_i and yiy_i there are cic_i special cat treats.

Task

Orange can choose exactly KK vertices, walk from the root of the tree to each of the chosen vertices along the paths from the root to the respective vertices and take all the cat treats along those paths. Of course, he can only take the treats on each edge once. Because Orange is a curious cat, he wants to know the maximum possible number of treats he could take by choosing the KK vertices optimally, if the root of the tree were vertex ii, for each ii from 11 to NN.

Input

The first line of the input contains two integers NN and KK, the number of vertices of the tree and the number of vertices Orange will choose, respectively. The next N1N - 1 lines contain three integers each, xi,yix_i, y_i and cic_i, describing the edges of the tree.

Output

On line ii for 1iN1 \leq i \leq N output the maximum number of treats Orange could take if the root of the tree were vertex ii.

Restrictions

  • 1KN100 0001 \leq K \leq N \leq 100 \ 000
  • 0ci1 000 000 0000 \leq c_i \leq 1 \ 000 \ 000 \ 000, for 1i<N1 \leq i < N
# Points Restrictions
1 8 N18N \leq 18
2 11 N200, K20N \leq 200, \ K \leq 20
3 17 N1 000, K100N \leq 1 \ 000, \ K \leq 100
4 20 N2 000N \leq 2 \ 000
5 12 K=1K = 1
6 32 No further restrictions.

Example

stdin

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

stdout

28
28
28
32
30
32
28
32
32
29
30

Explanation

If the root is vertex 11, then Orange can choose vertices 4,64, 6 and 99. The paths from the root to the chosen vertices are 1234,126,1791 − 2 − 3 − 4, 1 − 2 − 6, 1 − 7 − 9 and the number of treats along those paths is 5+3+4+5+6+5=285 + 3 + 4 + 5 + 6 + 5 = 28. Note that the treats on edge 121 − 2 are only counted once.

Log in or sign up to be able to send submissions!