Det finns $n$ städer, numrerade från 1 till $n$. Det finns också $n - 1$ dubbelriktade vägar som förbinder dessa städer, så att det för varje par av städer $x$ och $y$ finns en väg från $x$ till $y$. Den $i$-te vägen förbinder städerna $u_i$ och $v_i$, och har en kostnad $c_i$. Varje gång du passerar genom väg $i$ spenderar du $c_i$ mynt.
Du befinner dig nu i stad 1 och vill resa för att besöka alla städer. Varje sekund, om du befinner dig i stad $x$, kan du välja en stad $y$ som är direkt förbunden med stad $x$ via en väg, flytta till stad $y$ och betala kostnaden för respektive väg. Varje väg kan passeras högst två gånger. När du har besökt alla städer och befinner dig i stad 1 kan du avsluta din resa. Kostnaden för resan är den totala kostnaden för alla förflyttningar du gjort.
Det finns också ett heltal $k$. Under din resa kan du använda en gratiskupong en gång, vilket gör att dina följande $k$ förflyttningar inte kostar någonting.
För varje $k$ från 0 till $2n - 2$ ska du beräkna den minimala kostnaden för en resa som besöker alla städer och använder kupongen optimalt.
Indata
Den första raden innehåller ett enda heltal $t$ ($1 \le t \le 400$), antalet testfall. För varje testfall:
Den första raden innehåller ett heltal $n$ ($1 \le n \le 2000$), som anger antalet städer.
De följande $n - 1$ raderna beskriver vägarna. Den $i$-te av dessa rader innehåller tre heltal, $u_i$, $v_i$ och $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), som anger städerna som förbinds av den $i$-te vägen samt kostnaden för den vägen.
Det finns en väg mellan varje par av städer. Summan av $n$ överstiger inte $2000$.
Utdata
För varje testfall, skriv ut en rad som innehåller $2n - 1$ heltal: svaren för $k$ från 0 till $2n - 2$.
Exempel
Indata
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
Utdata
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Anmärkning
I det första testfallet kan vi alltid resa längs vägen $1, 2, 3, 2, 4, 5, 4, 2, 1$, med kostnadsföljden $2, 3, 3, 1, 3, 3, 1, 2$. De kostnadsfria segmenten för varje $k$ visas nedan.
| $k$ | kostnadsfritt segment | svar |
|---|---|---|
| 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 |