One Path

You are given a tree $T$ with $N$ vertices. Each edge has a positive integer weight.

You can perform the following operation on the tree.

• Delete an edge from the graph, then add a new edge between any two distinct vertices. The new edge must have the same weight as the deleted edge. The resulting graph does not need to be a tree.

The weight of a path is the sum of the weights of the edges on the path. The distance between two vertices $u$ and $v$ is the weight of the shortest path from $u$ to $v$, that is, the path with the minimum weight. If there is no such path, the distance is $0$.

The weight of a graph is the maximum distance between any two vertices.

Find the largest weight of the graph that can be obtained by performing the operation exactly $i$ times, for $i=0,1,\dots,K$.

The first line contains two space-separated integers $N$ and $K$. The $i$-th of the following $N-1$ lines contains three space-separated integers $u_i$, $v_i$, and $w_i$, which describe an undirected edge with weight $w_i$ that connects two different vertices $u_i$ and $v_i$. It is guaranteed that the edges form a tree.

Output $K+1$ space-separated integers. The $i$-th integer is the largest weight of the graph that can be obtained by performing the operation exactly $i-1$ times.

• $2\le N\le 2\,000$
• $0\le K\le 2\,000$
• $1\le u_i<v_i\le N$ ($1\le i\le N-1$)
• $1\le w_i\le 10^9$ ($1\le i\le N-1$)