Есть $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 |