У Нияза есть дерево из \(n\) вершин, пронумерованных от \(1\) до \(n\). Деревом называется связный граф без циклов.
Каждое ребро в этом дереве имеет строго больший нуля вес, обозначаемый целым числом. Степенью вершины называется количество ребер, смежных данной вершине.
Нияз не любит, когда вершины в дереве имеют слишком большие степени, поэтому он хочет найти для каждого \(x\) от \(0\) до \((n-1)\), ребра какого минимального суммарного веса нужно удалить, чтобы степени всех вершин стали не более \(x\).
Выходные данные
Выведите \(n\) целых чисел, разделенных пробелами: для каждого \(x = 0, 1, \ldots, (n-1)\) выведите минимальный суммарный вес такого множества ребер, при удалении которого степень всех вершин становится не больше \(x\).
Примечание
В первом примере в графе вершина \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 1
1 3 2
1 4 3
1 5 4
|
10 6 3 1 0
|
|
2
|
5
1 2 1
2 3 2
3 4 5
4 5 14
|
22 6 0 0 0
|