Maximizing Path Union Weight in a Weighted Tree

You are given a tree \( T=(V,E) \) with \( n=|V| \) vertices and weighted edges. For any two vertices \( u,v \), let \( \operatorname{path}(u,v) \) denote the unique set of edges on the simple path connecting \( u \) and \( v \) in \( T \).

Now, given a designated root \( r \) and any vertex subset \( V' \subseteq V \), define the path union by \[ E'(V')=\bigcup_{u\in V'} \operatorname{path}(r,u), \] and its weight as \[ w(V')=\sum_{e\in E'(V')}w(e). \]

For a given positive integer \( k \), define \[ f(r)=\max_{\substack{V'\subseteq V\\|V'|=k}}w(V'). \] That is, when the tree is rooted at \( r \), \( f(r) \) is the maximum achievable sum of edge weights over all choices of \( k \) vertices (the union being taken over the paths from \( r \) to every vertex in \( V' \)).

Your task is to compute \( f(r) \) for every possible choice of root \( r=1,2,\dots,n \).

Note: In the union \( E'(V') \) an edge is counted only once even if it appears in the paths to multiple chosen vertices.

inputFormat

The first line contains two integers \( n \) and \( k \) (the number of vertices and the size of the set to choose).

Each of the next \( n-1 \) lines contains three integers \( u, v, w \) indicating that there is an edge between vertices \( u \) and \( v \) with weight \( w \).

outputFormat

Output \( n \) integers: \( f(1), f(2), \dots, f(n) \) where \( f(r) \) is the maximum path union weight when the tree is rooted at \( r \). The answers can be output in one line separated by spaces.

sample

3 1
1 2 5
1 3 3

5 8 8