On $n$ kaupunkia, jotka on numeroitu 1:stä $n$:ään. Lisäksi on $n - 1$ kaksisuuntaista tietä, jotka yhdistävät nämä kaupungit siten, että jokaiselle kaupunkiparille $x$ ja $y$ on olemassa polku kaupungista $x$ kaupunkiin $y$. $i$:s tie yhdistää kaupungit $u_i$ ja $v_i$, ja sen hinta on $c_i$. Joka kerta, kun kuljet tien $i$ kautta, käytät $c_i$ kolikkoa.
Olet nyt kaupungissa 1 ja haluat matkustaa vieraillaksesi kaikissa kaupungeissa. Joka sekunti, jos olet kaupungissa $x$, voit valita kaupungin $y$, joka on suoraan yhteydessä kaupunkiin $x$ tiellä, siirtyä kaupunkiin $y$ ja maksaa kyseisen tien hinnan. Jokaisen tien kautta voi kulkea korkeintaan kaksi kertaa. Kun olet vieraillut kaikissa kaupungeissa ja olet kaupungissa 1, voit lopettaa matkasi. Matkan hinta on kaikkien tekemiesi siirtymien yhteenlaskettu hinta.
Annettuna on myös kokonaisluku $k$. Matkasi aikana voit käyttää kerran ilmaiskupongin, jolloin seuraavat $k$ siirtymääsi ovat ilmaisia.
Sinun tulee laskea jokaiselle $k$ väliltä 0 – $2n - 2$ pienin mahdollinen hinta matkalle, joka vierailee kaikissa kaupungeissa ja käyttää kupongin optimaalisesti.
Syöte
Ensimmäinen rivi sisältää yhden kokonaisluvun $t$ ($1 \le t \le 400$), testitapausten lukumäärän. Jokaiselle testitapaukselle:
Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2000$), joka ilmaisee kaupunkien määrän.
Seuraavat $n - 1$ riviä kuvaavat tiet. Näistä riveistä $i$:s sisältää kolme kokonaislukua, $u_i$, $v_i$ ja $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), jotka ilmaisevat $i$:nnen tien yhdistämät kaupungit sekä kyseisen tien hinnan.
Minkä tahansa kaupunkiparin välillä on polku. Lukujen $n$ summa ei ylitä arvoa $2000$.
Tuloste
Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää $2n - 1$ kokonaislukua: vastaukset luvulle $k$ välillä 0 – $2n - 2$.
Esimerkki
Syöte
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
Tuloste
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Huomautus
Ensimmäisessä testitapauksessa voimme aina kulkea polkua $1, 2, 3, 2, 4, 5, 4, 2, 1$, jonka hintajono on $2, 3, 3, 1, 3, 3, 1, 2$. Ilmaiset osuudet kullekin $k$ on esitetty alla.
| $k$ | ilmainen osuus | vastaus |
|---|---|---|
| 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 |