You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

「如果，如果，如果真的可以是那样的话，就好了啊。」

回想起自己做出的一个个选择，泠珞有时会想，自己是否有过更好的机会。

但是既然一切已经如此了，除了前进，别无他法。

无论结果是如何，接受结果，习得教训，然后……去争取更美好的未来。

那么，现在应该做的就是，尽可能避免，之后会走到的最坏结果了吧。

「规避风险。脚踏实地。做最可能实现的选择。」

「一定是的。」

题目描述

给定一棵有根带权树，结点以 $1\sim n$ 编号。根结点编号为 $1$，边权均为正整数。

定义这棵树的剖分为对于每个结点，选择一些儿子（可以都选或都不选）为重儿子的方案。重儿子和其父亲的边称为重边。不是重边的边称为轻边。

定义一个剖分是 $\textbf{\textit{i--}}$重的，当且仅当对于每个结点，其重儿子数量不超过 $i$。

定义一个剖分是 $\textbf{\textit{j--}}$轻的，当且仅当对于每条从根（编号为 $1$ 的结点）出发的简单路径，其经过的轻边的边权和不超过 $j$。

对于 $i=0,1,\cdots,n-1$，请求出最小的 $j$，使得存在一个 $\textit{i--}$重的剖分是 $\textit{j--}$轻的。

输入格式

第一行一个正整数 $n$，表示树的大小。

接下来 $n-1$ 行，每行三个正整数 $u_i,v_i,w_i$，表示编号为 $u_i,v_i$ 的结点间有一条边权为 $w_i$ 的边。

输出格式

一行 $n$ 个整数，表示 $i=0,1,2,\cdots,n-1$ 时的答案。

样例

5
1 2 1
1 3 1
2 4 1
2 5 1

2 1 0 0 0

样例 1 解释

对于样例 1，其中的树如下所示：

当 $i=0$ 时，只存在一种剖分，不存在任何重儿子或重边。一条从根出发经过轻边边权和最大的简单路径为 $1\textit{---}2\textit{---}4$，边权和为 $2$。

当 $i=1$ 时，可以采用如图所示的剖分，加粗结点（根除外）为重儿子。一条从根出发经过轻边边权和最大的简单路径为 $1\textit{---}2\textit{---}5$，经过轻边的边权和为 $1$。

当 $i\ge 2$ 时，可以令所有的非根结点为重儿子，因此任何从根出发经过最多轻边的简单路径只能经过 $0$ 条轻边，故轻边最大边权和为 $0$。

24
15 4 25
5 11 8
23 13 14
15 6 12
21 14 22
21 12 5
1 9 30
6 19 20
18 7 4
4 5 16
9 23 5
6 22 9
12 20 23
2 24 18
6 2 5
16 21 9
14 18 9
14 8 5
23 17 18
1 16 22
15 3 26
1 10 3
10 15 9

66 28 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例 2 解释

当 $i\ge 3$ 时，可以令所有的非根结点为重儿子，因此任何从根出发经过最多轻边的简单路径只能经过 $0$ 条轻边，故轻边最大边权和为 $0$。

当 $i=0,1,2$ 时，我有一个很简洁的解释，但是这里空白太小写不下。

10
4 8 407414868
3 9 875245582
10 3 548046335
2 8 163333320
7 5 320544242
5 3 504767824
6 7 431834202
9 4 639504669
9 1 968451452

3100843302 639504669 0 0 0 0 0 0 0 0

数据范围

本题开启捆绑测试。

对于 $100\%$ 的数据，$1\le n\le2\times10^5$，$1\le w_i\le 10^9$，保证输入是一棵树。