Dane jest drzewo $T$ składające się z $N$ wierzchołków. Każda krawędź ma dodatnią wagę całkowitą.

Możesz wykonać na danym drzewie następującą operację: * Usuń krawędź z grafu, a następnie dodaj nową krawędź pomiędzy dowolnymi dwoma różnymi wierzchołkami. Waga nowej krawędzi musi być taka sama jak waga usuniętej krawędzi. Wynikowy graf nie musi być drzewem.

Wagę ścieżki definiujemy jako sumę wag krawędzi znajdujących się na tej ścieżce. Odległość między dwoma wierzchołkami $u$ oraz $v$ definiujemy jako wagę najkrótszej ścieżki z $u$ do $v$ (ścieżki o minimalnej wadze). Jeśli taka ścieżka nie istnieje, przyjmujemy, że odległość wynosi $0$.

Waga grafu to maksimum z odległości pomiędzy dowolnymi dwoma wierzchołkami.

Twoim zadaniem jest znalezienie największej wagi grafu, jaką można uzyskać, wykonując operację dokładnie $i$ razy, dla $i = 0, 1, \dots, K$.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $N$ oraz $K$ oddzielone spacją.

Każda z kolejnych $N - 1$ linii zawiera trzy liczby całkowite $u_i$, $v_i$ oraz $w_i$ oddzielone spacjami, reprezentujące nieskierowaną krawędź łączącą dwa różne wierzchołki $u_i$ oraz $v_i$ o wadze $w_i$.

Gwarantuje się, że krawędzie tworzą drzewo.

• $2 \le N \le 2000$
• $0 \le K \le 2000$
• $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$)

Wyjście

Wypisz $K + 1$ liczb całkowitych oddzielonych spacjami. $i$-ta liczba powinna być równa największej wadze grafu, jaką można uzyskać, wykonując operację dokładnie $i - 1$ razy.

Przykład

Wejście 1

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

Wyjście 1

14 16

Wejście 2

7 2
1 2 4
2 3 6
2 4 2
4 5 5
2 6 1
4 7 3

Wyjście 2

13 20 21