Terdapat $n$ kota, yang dinomori dari 1 hingga $n$. Terdapat pula $n - 1$ jalan dua arah yang menghubungkan kota-kota ini, sehingga untuk setiap dua kota $x$ dan $y$, terdapat sebuah jalur dari $x$ ke $y$. Jalan ke-$i$ menghubungkan kota $u_i$ dan $v_i$, serta memiliki biaya $c_i$. Setiap kali Anda melewati jalan $i$, Anda menghabiskan $c_i$ koin.
Saat ini Anda berada di kota 1 dan ingin melakukan perjalanan untuk mengunjungi semua kota. Setiap detik, jika Anda berada di kota $x$, Anda dapat memilih sebuah kota $y$ yang terhubung langsung dengan kota $x$ melalui sebuah jalan, berpindah ke kota $y$, dan membayar biaya jalan yang bersangkutan. Setiap jalan dapat dilewati paling banyak dua kali. Ketika Anda telah mengunjungi semua kota dan berada di kota 1, Anda dapat mengakhiri perjalanan Anda. Biaya perjalanan adalah total biaya dari semua perpindahan yang Anda lakukan.
Terdapat pula sebuah bilangan bulat $k$. Selama perjalanan, Anda dapat menggunakan kupon gratis satu kali, yang membuat $k$ perpindahan Anda berikutnya tidak dikenakan biaya.
Untuk setiap $k$ dari 0 hingga $2n - 2$, Anda harus menghitung biaya minimum dari perjalanan yang mengunjungi semua kota dan menggunakan kupon secara optimal.
Masukan
Baris pertama berisi sebuah bilangan bulat $t$ ($1 \le t \le 400$), yaitu banyaknya kasus uji. Untuk setiap kasus uji:
Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 2000$), yang menyatakan banyaknya kota.
$n - 1$ baris berikutnya menjelaskan jalan-jalan tersebut. Baris ke-$i$ dari baris-baris ini berisi tiga bilangan bulat, $u_i$, $v_i$, dan $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), yang menyatakan kota-kota yang dihubungkan oleh jalan ke-$i$ dan biaya jalan tersebut.
Terdapat jalur di antara setiap pasang kota. Jumlah dari $n$ tidak melebihi $2000$.
Keluaran
Untuk setiap kasus uji, keluarkan satu baris yang berisi $2n - 1$ bilangan bulat: jawaban untuk $k$ dari 0 hingga $2n - 2$.
Contoh
Masukan
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
Keluaran
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Catatan
Pada kasus uji pertama, kita selalu dapat melakukan perjalanan sepanjang jalur $1, 2, 3, 2, 4, 5, 4, 2, 1$, dengan barisan biaya $2, 3, 3, 1, 3, 3, 1, 2$. Segmen bebas biaya untuk setiap $k$ ditunjukkan di bawah ini.
| $k$ | segmen bebas biaya | jawaban |
|---|---|---|
| 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 |