Ci sono $n$ città, numerate da 1 a $n$. Ci sono anche $n - 1$ strade bidirezionali che collegano queste città, in modo tale che per ogni coppia di città $x$ e $y$ esista un cammino da $x$ a $y$. La $i$-esima strada collega le città $u_i$ e $v_i$ e ha un costo $c_i$. Ogni volta che percorri la strada $i$, spendi $c_i$ monete.
Ora ti trovi nella città 1 e vuoi viaggiare per visitare tutte le città. Ogni secondo, se ti trovi nella città $x$, puoi scegliere una città $y$ direttamente collegata alla città $x$ da una strada, spostarti nella città $y$ e pagare il costo della rispettiva strada. Ogni strada può essere percorsa al massimo due volte. Quando hai visitato tutte le città e ti trovi nella città 1, puoi concludere il tuo viaggio. Il costo del viaggio è il costo totale di tutte le mosse che hai effettuato.
C'è anche un intero $k$. Durante il tuo viaggio puoi utilizzare una sola volta un buono gratuito, rendendo gratuite le tue successive $k$ mosse.
Per ogni $k$ da 0 a $2n - 2$, devi calcolare il costo minimo di un viaggio che visiti tutte le città e utilizzi il buono in modo ottimale.
Input
La prima riga contiene un singolo intero $t$ ($1 \le t \le 400$), il numero di casi di test. Per ciascun caso di test:
La prima riga contiene un intero $n$ ($1 \le n \le 2000$), che indica il numero di città.
Le successive $n - 1$ righe descrivono le strade. La $i$-esima di queste righe contiene tre interi, $u_i$, $v_i$ e $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), che indicano le città collegate dalla $i$-esima strada e il costo di tale strada.
Esiste un cammino tra qualsiasi coppia di città. La somma di $n$ non supera $2000$.
Output
Per ciascun caso di test, stampa una riga contenente $2n - 1$ interi: le risposte per $k$ da 0 a $2n - 2$.
Esempio
Input
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
Output
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Note
Nel primo caso di test possiamo sempre viaggiare lungo il cammino $1, 2, 3, 2, 4, 5, 4, 2, 1$, con la sequenza dei costi $2, 3, 3, 1, 3, 3, 1, 2$. I segmenti gratuiti per ciascun $k$ sono mostrati di seguito.
| $k$ | segmento gratuito | risposta |
|---|---|---|
| 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 |