Niyaz 有一棵树,其顶点为 $$$n$$$,编号从 $$$1$$$ 到 $$$n$$$。树是没有环的连通图。
该树中的每条边都具有严格的正整数权重。顶点的度数是与该顶点相邻的边的数量。
Niyaz 不喜欢树中的顶点度数太大。对于从$$$0$$$到$$$(n-1)$$$的每一个$$$x$$$,他想要找到要删除的一组边的最小总权重,使得所有顶点的度数最多变为$$$x$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 250\,000$$$) — Niyaz 树中的顶点数。
接下来的 $$$(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$$$。
示例
输入 #1
5 1 2 1 1 3 2 1 4 3 1 5 4
输出 #1
10 6 3 1 0
输入 #2
5 1 2 1 2 3 2 3 4 5 4 5 14
输出 #2
22 6 0 0 0
注意
在第一个示例中,顶点 $$$1$$$ 与所有其他顶点相连。因此,对于每个 $$$x$$$,您应该删除从顶点 $$$1$$$ 发出的 $$$(4-x)$$$ 最轻边,因此答案为 $$$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$$$。