题目描述

小明正在观察异地恋。

这个交通不便的国家共有 $n$ 个城市，有 $n-1$ 条道路将它们连接起来，每条道路的长度是 $w_i$。小明从这 $n$ 个城市中每个城市选择了一个人，经过短时间的观察，小明发现这 $n$ 个人中的每个人要么单身，要么ta的伴侣在另一个城市。有些时候事情就是那么巧，有一些异地恋情侣恰好就是小明选择的 $n$ 个人中的两个。

不过，由于去考察异地恋的双方分别是谁就有点打探别人的隐私了，所以小明果断打住了，转而去研究了另一个问题。对于一对异地恋的情侣，记他们的遥远度为两人所在城市之间最短路径的长度。假设小明的运气足够好，这 $n$ 个人中恰好有 $k$ 对情侣，那么这 $n$ 个人的总遥远度就是这 $k$ 对情侣的遥远度之和。

股票的事情最终结果不尽人意，给了小明很大打击，小明早就成为了悲观主义者。他想知道，在已知 $n$ 个人中恰有 $k$ 对情侣，但不知道分别是谁的前提下，在所有可能的情况中，遥远度的最大值是多少。

当然，小明对自己的运气到底有多好没什么信心，于是他想要对每个 $k=1,2,\dots,\lfloor\frac n2\rfloor$ 求出这个遥远度的最大值。

输入格式

第一行一个正整数 $n$，表示城市数量。

之后的 $n-1$ 行，每行三个正整数 $u,v,w$，表示城市 $u$ 与城市 $v$ 之间有一条长度为 $w$ 的边。

输出格式

一行 $\lfloor\frac n2\rfloor$ 个数，表示 $k=1,2,\dots,\lfloor\frac n2\rfloor$ 时遥远度的最大值。

输入输出样例

样例输入1

7
1 3 99
2 3 82
3 4 4
4 5 43
5 6 5
4 7 3

样例输出1

181 280 287

其余样例见下发文件，其分别满足下表每一个子任务的限制。

数据范围

对于 $100\%$ 的数据，$1\le n\le10^6,1\le w\le10^6$。保证输入的是一棵树。

本题采用子任务测试，且会有极大的合理子任务依赖。只有你通过了一个子任务中的所有测试点，且通过了其所有依赖子任务时，才可得到该子任务的分数。