Description

The kingdom of Temeria is one of the most powerful kingdoms in the North, with its capital in the city of Vizima. Triss, a sorceress living in Vizima, has discovered strong magical anomalies and decided to investigate their source throughout the kingdom of Temeria.

Temeria has $n$ cities, numbered from 1 to $n$. The capital, Vizima, has number 1. The cities are connected by $n-1$ bidirectional roads. The $i$-th road connects cities $u_i$ and $v_i$ and has length $w_i$. It is guaranteed that Triss can reach any city from any other city using these roads.

Triss plans to start and end her journey in Vizima, visiting all $n$ cities. Triss can travel along roads, but this is slow. She has $k$ teleportation crystals, which allow her to instantly travel between cities.

At any moment, Triss can leave a crystal in her current city. Later, she can use a previously left crystal to instantly return to the city where she left it, via the shortest path. After use, the crystal is destroyed. Triss can leave and use crystals in any order. Unfortunately, teleportation is not without consequences. Specifically, if Triss, while in city $a$, uses a crystal to travel to city $b$, then all cities on the shortest path between $a$ and $b$, including $a$ and $b$ themselves, will be magically marked. Further travel through these marked cities via other teleportation routes is not possible.

Help Triss. For each $j$ from 1 to $k$ inclusive, determine the minimum distance Triss needs to travel to visit all cities in the kingdom and return to Vizima, using at most $j$ crystals.

Input

The first line of input contains two integers $n$ and $k$ ($2 \le n \le 500000$; $1 \le k \le n$), the number of cities and the number of teleportation crystals Triss has. The following $n-1$ lines describe the roads: they contain three integers $u_i, v_i, w_i$ ($1 \le u_i, v_i < n$; $1 \le w_i \le 10^9$), the numbers of the cities connected by the $i$-th road, and the length of this road, respectively.

Output

Output $k$ numbers, where the $j$-th number is the minimum distance Triss needs to travel to visit all cities and return to Vizima, using at most $j$ crystals.

Subtasks

• [1] A full binary tree in subtask 5 is a tree consisting of $2^s - 1$ vertices (for some $s$), where for each $i$ from 1 to $2^{s-1}-1$, there exist edges $(i, 2i)$ and $(i, 2i+1)$.
• [2] A special graph in subtask 7 is a tree consisting of an odd number of vertices $n$, where for each $i$ from 1 to $2^{\lfloor \log_2 n \rfloor - 1}$, there exist edges $(1, 2i)$ and $(2i, 2i+1)$.

Examples

Input 1

5 1
1 2 1
1 3 1
3 4 1
3 5 1

Output 1

6

Input 2

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

Output 2

86
85

Note

In the first example, the optimal route for Triss is as follows. * Triss leaves a crystal in city 1, then travels along the path $1 \to 2 \to 1 \to 3 \to 4 \to 3 \to 5$, after which she uses the crystal and instantly returns to city 1.

In the second example, the optimal routes look like this: * Triss travels along the path $1 \to 5 \to 1$, then leaves a crystal in city 1, then travels along the path $1 \to 9 \to 1 \to 2 \to 3 \to 7 \to 3 \to 4 \to 8 \to 4 \to 6 \to 10$ and uses the crystal in city 1. The length of this route is 86, and Triss uses exactly one crystal.

In another route, Triss will need to use two crystals, let's call them $x$ and $y$. Triss leaves crystal $x$ in city 1; Then she travels along the path $1 \to 5 \to 1 \to 9 \to 1 \to 2 \to 3 \to 7 \to 3 \to 4 \to 6$; In city 6, Triss leaves crystal $y$; Then she travels $6 \to 10$ and uses crystal $y$, returning to city 6; She travels along the path $6 \to 4 \to 8$; And finishes her journey by using crystal $x$.