Description

为了建立伟大的三叶虫帝国，不屈的三叶虫给了你一棵大小为 $n$ 的边带正权的树 $T$，对于每个 $i=1...\lfloor\frac n2\rfloor$ 求完全图 $G$ 的大小为 $i$ 的最大权匹配，其中在 $G$ 中连接 $i$ 和 $j$ 的边权与 $T$ 中 $i$ 到 $j$ 的距离相等。

Input Format

第一行一个正整数 $n$。

接下来 $n-1$ 行，每行三个正整数 $u,v,w$，表示树上一条边。

Output Format

一行 $\lfloor\frac n2\rfloor$ 个整数，表示答案。

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

181 280 287

Hint

样例中，对于匹配大小分别为 $1,2,3$ 的情况，最优的方案分别为 $(1,2)$，$(1,5),(2,6)$，$(1,7),(2,5),(3,6)$。请注意这并非唯一的方案。

对于全部的数据，$1\le n,w\le 10^6$。