Ruyi Ji 有一棵树，顶点编号为 $1$ 到 $n$，每条边都有一个权重。 对于每个 $k \le (n - 1)$，他要求你找出包含 $k$ 条边的匹配中，总权重最大的匹配（如果存在的话）。

输入格式

第一行包含一个整数 $n$：树的顶点数 ($2 \le n \le 200\,000$)。 接下来的 $n - 1$ 行，每行包含三个整数 $u_i, v_i, w_i$，描述一条连接 $u_i$ 和 $v_i$、权重为 $w_i$ 的边 ($1 \le u_i, v_i \le n, u_i \neq v_i, -10^9 \le w_i \le 10^9$)。 保证给定的图是一棵树。

输出格式

输出 $n - 1$ 个整数：分别对应包含 $1, 2, \dots, n - 1$ 条边的匹配的最大总权重。如果对于当前的 $k$ 不存在这样的匹配，则输出 “?”。

样例

样例输入 1

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

样例输出 1

5 6 ? ?

样例输入 2

10
2 8 -5
5 10 5
3 4 -5
1 6 5
3 9 5
1 7 -3
4 8 -5
10 8 -5
1 8 -3

样例输出 2

5 10 15 10 ? ? ? ? ?

样例输入 3

2
1 2 35

样例输出 3

35

说明

在第一个样例中，对于 $k = 1$，你应该选择权重为 $5$ 的边 $(2, 3)$。对于 $k = 2$，你应该选择两条边 $(2, 4)$ 和 $(3, 5)$，总权重为 $6$。不存在边数更多的匹配。