本题献给现任 ICPC 冠军。谨以此题，由 2020 年 ICPC 冠军（并希望是 2023 年 ICPC 冠军）献给 2021 年（并希望是 2022 年）的 ICPC 冠军，致以爱意。

给定一棵包含 $n$ 个顶点的带权树 $T$。定义 $d_{uv}$ 为 $T$ 中 $u$ 和 $v$ 之间唯一简单路径上所有边的权重之和。考虑一个完全加权图 $G$，其中边 $(u, v)$ 的权重为 $d_{uv}$。

对于 $1$ 到 $\lfloor \frac{n}{2} \rfloor$ 之间的每一个 $k$，计算图 $G$ 中大小为 $k$ 的匹配的最大总权重。回想一下，大小为 $k$ 的匹配是指包含 $k$ 条边的集合，且其中任意两条边都没有公共顶点。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)，表示树的大小。

接下来的 $n - 1$ 行描述树的边。第 $i$ 行包含三个整数 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 10^8$)，表示 $T$ 中存在一条权重为 $w_i$ 的边 $(u_i, v_i)$。

保证给定的边构成一棵树。

输出格式

输出 $\lfloor \frac{n}{2} \rfloor$ 个整数，分别表示 $G$ 中对应大小的匹配的最大总权重。

样例

样例输入 1

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

样例输出 1

181 280 287