Det er $n$ byer, nummerert fra 1 til $n$. Det er også $n - 1$ toveis veier som forbinder disse byene, slik at det for hver to byer $x$ og $y$ finnes en sti fra $x$ til $y$. Den $i$-te veien forbinder byene $u_i$ og $v_i$, og har en kostnad $c_i$. Hver gang du passerer gjennom vei $i$, bruker du $c_i$ mynter.
Du er nå i by 1 og ønsker å reise for å besøke alle byene. Hvert sekund, hvis du er i by $x$, kan du velge en by $y$ som er direkte forbundet med by $x$ via en vei, flytte til by $y$ og betale kostnaden for den aktuelle veien. Hver vei kan passeres høyst to ganger. Når du har besøkt alle byene og befinner deg i by 1, kan du avslutte reisen. Kostnaden for reisen er den totale kostnaden for alle trekkene du har gjort.
Det finnes også et heltall $k$. I løpet av reisen kan du bruke en gratiskupong én gang, som gjør at de påfølgende $k$ trekkene dine ikke koster noe.
For hver $k$ fra 0 til $2n - 2$ skal du beregne den minimale kostnaden for en reise som besøker alle byene og bruker kupongen optimalt.
Inndata
Den første linjen inneholder et enkelt heltall $t$ ($1 \le t \le 400$), antallet testtilfeller. For hvert testtilfelle:
Den første linjen inneholder et heltall $n$ ($1 \le n \le 2000$), som angir antallet byer.
De neste $n - 1$ linjene beskriver veiene. Den $i$-te av disse linjene inneholder tre heltall, $u_i$, $v_i$ og $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), som angir byene som er forbundet av den $i$-te veien og kostnaden for denne veien.
Det finnes en sti mellom ethvert par av byer. Summen av $n$ overstiger ikke $2000$.
Utdata
For hvert testtilfelle skal du skrive ut én linje som inneholder $2n - 1$ heltall: svarene for $k$ fra 0 til $2n - 2$.
Eksempel
Inndata
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
Merk
I det første testtilfellet kan vi alltid reise langs stien $1, 2, 3, 2, 4, 5, 4, 2, 1$, med kostnadsfølgen $2, 3, 3, 1, 3, 3, 1, 2$. De kostnadsfrie segmentene for hver $k$ er vist nedenfor.
| $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 |