在泗水市，有 \(N\) 个路口（编号从 \(0\) 到 \(N-1\) ）。这些路口由 \(N-1\) 条双向道路连接（编号从 \(0\) 到 \(N-2\) ），因此通过这些道路，任意一对路口之间都有一条唯一的路径。 \(i\) 号道路（ \(0 \le i \le N-2\) ）连接着 \(U[i]\) 号和 \(V[i]\) 号路口。

为了提高环保意识，泗水市长 Pak Dengklek 计划举办无车日。为了鼓励该活动，Pak Dengklek 将组织封路。Pak Dengklek 将首先选择一个非负整数 \(k\) ，然后封闭一些道路，以使每个路口只能直接连接至多 \(k\) 条未封闭的道路。封闭 \(i\) 号道路的成本为 \(W[i]\) 。

请你帮助 Pak Dengklek 对每个可能的非负整数 \(k\) （ \(0 \le k \le N-1\) ）计算封闭道路的最低总成本。

已将原题的交互方式转化为传统方式

第一行一个整数 \(N\) 。

接下来 \(N-1\) 行，每行三个整数 \(U[i],V[i],W[i]\) ，表示第 \(i\) 条道路。

输出一行 \(N\) 个整数，第 \(k(0\le k\le N-1)\) 个数是使得每个路口与至多 \(k\) 条未封闭道路直接连接的最低总成本。

样例1解释

这个例子中共有 \(5\) 个路口和 \(4\) 条道路，分别连接着路口 \((0,1),(0,2),(0,3)\) 和 \((2,4)\) ，封闭它们的成本依次为 \(1,4,3\) 和 \(2\) 。

为了得到最低的总成本：

• 如果 Pak_Dengklek 选择 \(k=0\) ，那么所有道路都需要封闭，总成本为 \(1+4+3+2=10\) ；
• 如果 Pak_Dengklek 选择 \(k=1\) ，那么需要封闭 \(0\) 号道路和 \(1\) 号道路，总成本为 \(1+4=5\) ；
• 如果 Pak_Dengklek 选择 \(k=2\) ，那么需要封闭 \(0\) 号道路，总成本为 \(1\) ；
• 如果 Pak_Dengklek 选择 \(k=3\) 或 \(k=4\) ，那么没有道路需要封闭。

因此输出答案 \(10,5,1,0,0\) 。

样例2解释

这个例子中共有 \(4\) 个路口和 \(3\) 条道路，分别连接着路口 \((0,1),(2,0)\) 和 \((0,3)\) ，封闭它们的成本依次为 \(5,10\) 和 \(5\) 。

为了得到最低的总成本:

• 如果 PakDengklek 选择 \(k=0\) ，那么所有道路都需要封闭，总成本为 \(5+10+5=20\) ；
• 如果 PakDengklek 选择 \(k=1\) ，那么需要封闭 \(0\) 号道路和 \(2\) 号道路，总成本为 \(5+5=10\) ；
• 如果 PakDengklek 选择 \(k=2\) ，那么需要封闭 \(0\) 号道路或 \(2\) 号道路，总成本为 \(5\) ；
• 如果 PakDengklek 选择 \(k=3\) ，那么没有道路需要封闭。

因此输出答案 \(20,10,5,0\) 。

数据范围

• \(2 \le N \le 10^5\)
• \(0 \le U[i],V[i] \le N-1\) \((0 \le i \le N-2)\)
• 任意一对路口可以通过道路互相到达。
• \(1 \le W[i] \le 10^9\) \((0 \le i \le N-2)\) 。

子任务

1. (5 分)： \(U[i]=0\) \((0 \le i \le N-2)\)
2. (7 分)： \(U[i]=i\) ， \(V[i]=i+1\) \((0 \le i \le N-2)\)
3. (14 分)： \(N \le 200\)
4. (10 分)： \(N \le 2000\)
5. (17 分)： \(W[i]=1\) \((0 \le i \le N-2)\)
6. (25 分)： \(W[i] \le 10\) \((0 \le i \le N-2)\)
7. (22 分)： 无附加限制

有原题CF1119F，数据范围稍有区别但没有本质区别