F. Нияз и маленькие степени
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Нияза есть дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Деревом называется связный граф без циклов.

Каждое ребро в этом дереве имеет строго больший нуля вес, обозначаемый целым числом. Степенью вершины называется количество ребер, смежных данной вершине.

Нияз не любит, когда вершины в дереве имеют слишком большие степени, поэтому он хочет найти для каждого $$$x$$$ от $$$0$$$ до $$$(n-1)$$$, ребра какого минимального суммарного веса нужно удалить, чтобы степени всех вершин стали не более $$$x$$$.

Входные данные

Первая строка содержит единственное целое число $$$n$$$ ($$$2 \le n \le 250\,000$$$) — количество вершин в дереве Нияза.

Каждая из следующих $$$(n - 1)$$$ строк содержит три целых числа $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \le a, b \le n$$$, $$$1 \leq c \leq 10^6$$$) — номера вершин, которые соединяет очередное ребро дерева и его вес, соответственно. Гарантируется, что заданные ребра образуют дерево.

Выходные данные

Выведите $$$n$$$ целых чисел, разделенных пробелами: для каждого $$$x = 0, 1, \ldots, (n-1)$$$ выведите минимальный суммарный вес такого множества ребер, при удалении которого степень всех вершин становится не больше $$$x$$$.

Примеры
Входные данные
5
1 2 1
1 3 2
1 4 3
1 5 4
Выходные данные
10 6 3 1 0
Входные данные
5
1 2 1
2 3 2
3 4 5
4 5 14
Выходные данные
22 6 0 0 0
Примечание

В первом примере в графе вершина $$$1$$$ соединена со всеми остальными. Таким образом, для всеx $$$x$$$ достаточно удалить $$$(4-x)$$$ ребер минимальной стоимости, исходящих из вершины $$$1$$$, таким образом, ответы равны $$$1+2+3+4$$$, $$$1+2+3$$$, $$$1+2$$$, $$$1$$$, и $$$0$$$.

Во втором примере при $$$x=0$$$ необходимо удалить все ребра, при $$$x=1$$$ достаточно удалить два ребра веса $$$1$$$ и $$$5$$$, а при $$$x \geq 2$$$ ребра удалять необязательно, поэтому ответы равны $$$1+2+5+14$$$, $$$1+5$$$, $$$0$$$, $$$0$$$ и $$$0$$$.