Það eru $n$ borgir, númeraðar frá 1 til $n$. Einnig eru $n - 1$ tvístefnuvegir sem tengja þessar borgir, þannig að fyrir sérhverjar tvær borgir $x$ og $y$ er til vegur frá $x$ til $y$. $i$-ti vegurinn tengir borgirnar $u_i$ og $v_i$ og hefur kostnaðinn $c_i$. Í hvert sinn sem þú ferð um veg $i$ eyðir þú $c_i$ myntum.
Þú ert núna í borg 1 og vilt ferðast til að heimsækja allar borgirnar. Á hverri sekúndu, ef þú ert í borg $x$, geturðu valið borg $y$ sem er beintengd við borg $x$ með vegi, fært þig yfir í borg $y$ og greitt kostnaðinn fyrir viðkomandi veg. Hvern veg má fara í mesta lagi tvisvar. Þegar þú hefur heimsótt allar borgirnar og ert í borg 1 geturðu lokið ferðalaginu. Kostnaður ferðalagsins er heildarkostnaður allra færzlna sem þú gerðir.
Einnig er gefin heiltala $k$. Á ferðalagi þínu geturðu notað ókeypis afsláttarmiða einu sinni, sem gerir það að verkum að næstu $k$ færslur þínar kosta ekkert.
Fyrir hvert $k$ frá 0 til $2n - 2$ áttu að reikna lágmarkskostnað ferðalags sem heimsækir allar borgirnar og notar afsláttarmiðann á sem bestan hátt.
Inntak
Fyrsta línan inniheldur eina heiltölu $t$ ($1 \le t \le 400$), fjölda prófunartilvika. Fyrir hvert prófunartilvik:
Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 2000$), sem táknar fjölda borga.
Næstu $n - 1$ línur lýsa vegunum. $i$-ta línan af þessum línum inniheldur þrjár heiltölur, $u_i$, $v_i$ og $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), sem tákna borgirnar sem $i$-ti vegurinn tengir og kostnað þess vegar.
Það er vegur á milli sérhvers pars af borgum. Summa $n$ fer ekki yfir $2000$.
Úttak
Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $2n - 1$ heiltölur: svörin fyrir $k$ frá 0 til $2n - 2$.
Dæmi
Inntak
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
Úttak
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Athugasemd
Í fyrsta prófunartilvikinu getum við alltaf ferðast eftir leiðinni $1, 2, 3, 2, 4, 5, 4, 2, 1$, með kostnaðarrununni $2, 3, 3, 1, 3, 3, 1, 2$. Kostnaðarlausu bútar fyrir hvert $k$ eru sýndir hér að neðan.
| $k$ | kostnaðarlaus bútur | 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 |