Istnieje $n$ miast, ponumerowanych od 1 do $n$. Istnieje również $n - 1$ dwukierunkowych dróg łączących te miasta, tak że dla każdych dwóch miast $x$ i $y$ istnieje ścieżka z $x$ do $y$. $i$-ta droga łączy miasta $u_i$ oraz $v_i$ i ma koszt $c_i$. Za każdym razem, gdy przechodzisz przez drogę $i$, wydajesz $c_i$ monet.
Jesteś teraz w mieście 1 i chcesz odbyć podróż, aby odwiedzić wszystkie miasta. W każdej sekundzie, jeśli znajdujesz się w mieście $x$, możesz wybrać miasto $y$ połączone bezpośrednio z miastem $x$ drogą, przemieścić się do miasta $y$ i zapłacić koszt odpowiedniej drogi. Każda droga może zostać przebyta co najwyżej dwa razy. Gdy odwiedzisz już wszystkie miasta i będziesz w mieście 1, możesz zakończyć swoją podróż. Kosztem podróży jest łączny koszt wszystkich wykonanych ruchów.
Dana jest również liczba całkowita $k$. Podczas podróży możesz raz użyć darmowego kuponu, dzięki czemu kolejne $k$ ruchów nic nie kosztuje.
Dla każdego $k$ od 0 do $2n - 2$ należy obliczyć minimalny koszt podróży, która odwiedza wszystkie miasta i optymalnie wykorzystuje kupon.
Wejście
Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 400$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:
Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 2000$), oznaczającą liczbę miast.
Kolejne $n - 1$ wierszy opisuje drogi. $i$-ty z tych wierszy zawiera trzy liczby całkowite $u_i$, $v_i$ oraz $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), oznaczające miasta połączone $i$-tą drogą oraz koszt tej drogi.
Pomiędzy każdą parą miast istnieje ścieżka. Suma wartości $n$ nie przekracza $2000$.
Wyjście
Dla każdego przypadku testowego wypisz jeden wiersz zawierający $2n - 1$ liczb całkowitych: odpowiedzi dla $k$ od 0 do $2n - 2$.
Przykład
Wejście
2 5 1 2 2 2 3 3 2 4 1 4 5 3 7 1 2 1 1 3 1 1 4 4 3 5 5 3 6 1 6 7 4
Wyjście
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Uwaga
W pierwszym przypadku testowym zawsze możemy podróżować wzdłuż ścieżki $1, 2, 3, 2, 4, 5, 4, 2, 1$ o ciągu kosztów $2, 3, 3, 1, 3, 3, 1, 2$. Darmowe fragmenty dla każdego $k$ pokazano poniżej.
| $k$ | darmowy fragment | odpowiedź |
|---|---|---|
| 0 | $[]$ | 18 |
| 1 | $[3]$ | 15 |
| 2 | $[3, 3]$ | 12 |
| 3 | $[2, 3, 3]$ | 10 |
| 4 | $[3, 3, 1, 3]$ | 8 |
| 5 | $[3, 3, 1, 3, 3]$ | 5 |
| 6 | $[2, 3, 3, 1, 3, 3]$ | 3 |
| 7 | $[2, 3, 3, 1, 3, 3, 1]$ | 2 |
| 8 | $[2, 3, 3, 1, 3, 3, 1, 2]$ | 0 |