Є $n$ міст, пронумерованих від 1 до $n$. Також є $n - 1$ двосторонніх доріг, що з'єднують ці міста так, що для будь-яких двох міст $x$ і $y$ існує шлях із $x$ до $y$. $i$-та дорога з'єднує міста $u_i$ та $v_i$ і має вартість $c_i$. Щоразу, проходячи дорогою $i$, ви витрачаєте $c_i$ монет.
Зараз ви перебуваєте в місті 1 і хочете здійснити подорож, щоб відвідати всі міста. Щосекунди, перебуваючи в місті $x$, ви можете вибрати місто $y$, яке напряму з'єднане з містом $x$ дорогою, переміститися в місто $y$ і заплатити вартість відповідної дороги. Кожною дорогою можна пройти щонайбільше два рази. Коли ви відвідали всі міста і перебуваєте в місті 1, ви можете завершити подорож. Вартість подорожі дорівнює сумарній вартості всіх здійснених вами переміщень.
Також задано ціле число $k$. Під час подорожі ви можете один раз використати безкоштовний купон, завдяки чому наступні $k$ ваших переміщень не матимуть вартості.
Для кожного $k$ від 0 до $2n - 2$ вам потрібно обчислити мінімальну вартість подорожі, яка відвідує всі міста та оптимально використовує купон.
Вхідні дані
Перший рядок містить одне ціле число $t$ ($1 \le t \le 400$) — кількість тестових випадків. Для кожного тестового випадку:
Перший рядок містить ціле число $n$ ($1 \le n \le 2000$), що позначає кількість міст.
Наступні $n - 1$ рядків описують дороги. $i$-й із цих рядків містить три цілі числа $u_i$, $v_i$ та $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), що позначають міста, з'єднані $i$-ю дорогою, та вартість цієї дороги.
Між будь-якою парою міст існує шлях. Сума $n$ не перевищує $2000$.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить $2n - 1$ цілих чисел: відповіді для $k$ від 0 до $2n - 2$.
Приклад
Вхідні дані
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
Вихідні дані
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Примітка
У першому тестовому випадку ми завжди можемо подорожувати шляхом $1, 2, 3, 2, 4, 5, 4, 2, 1$ із послідовністю вартостей $2, 3, 3, 1, 3, 3, 1, 2$. Безкоштовні відрізки для кожного $k$ показано нижче.
| $k$ | безкоштовний відрізок | відповідь |
|---|---|---|
| 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 |