Có $n$ thành phố, được đánh số từ 1 đến $n$. Ngoài ra còn có $n - 1$ con đường hai chiều kết nối các thành phố này, sao cho với mọi cặp thành phố $x$ và $y$, luôn tồn tại một đường đi từ $x$ đến $y$. Con đường thứ $i$ nối thành phố $u_i$ và $v_i$, và có chi phí $c_i$. Mỗi lần đi qua con đường $i$, bạn phải trả $c_i$ đồng xu.
Hiện tại bạn đang ở thành phố 1 và muốn đi du lịch để thăm tất cả các thành phố. Mỗi giây, nếu đang ở thành phố $x$, bạn có thể chọn một thành phố $y$ được nối trực tiếp với thành phố $x$ bằng một con đường, di chuyển đến thành phố $y$ và trả chi phí của con đường tương ứng. Mỗi con đường chỉ có thể đi qua tối đa hai lần. Khi bạn đã thăm tất cả các thành phố và đang ở thành phố 1, bạn có thể kết thúc chuyến đi của mình. Chi phí của chuyến đi là tổng chi phí của tất cả các bước di chuyển mà bạn đã thực hiện.
Ngoài ra còn có một số nguyên $k$. Trong chuyến đi, bạn có thể sử dụng phiếu miễn phí một lần, giúp $k$ bước di chuyển tiếp theo của bạn không tốn chi phí.
Với mỗi $k$ từ 0 đến $2n - 2$, bạn cần tính chi phí nhỏ nhất của một chuyến đi thăm tất cả các thành phố và sử dụng phiếu miễn phí một cách tối ưu.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 400$), số lượng bộ test. Với mỗi bộ test:
Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 2000$), biểu thị số lượng thành phố.
$n - 1$ dòng tiếp theo mô tả các con đường. Dòng thứ $i$ trong các dòng này chứa ba số nguyên $u_i$, $v_i$ và $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), biểu thị các thành phố được nối bởi con đường thứ $i$ và chi phí của con đường đó.
Luôn có đường đi giữa mọi cặp thành phố. Tổng của $n$ không vượt quá $2000$.
Kết quả
Với mỗi bộ test, in ra một dòng chứa $2n - 1$ số nguyên: đáp án cho $k$ từ 0 đến $2n - 2$.
Ví dụ
Dữ liệu vào
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
Kết quả
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Ghi chú
Ở bộ test đầu tiên, ta luôn có thể đi theo hành trình $1, 2, 3, 2, 4, 5, 4, 2, 1$ với dãy chi phí $2, 3, 3, 1, 3, 3, 1, 2$. Các đoạn được miễn phí ứng với mỗi $k$ đượcแสดง dưới đây.
| $k$ | đoạn miễn phí | đáp án |
|---|---|---|
| 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 |