Niyaz and Small Degrees

Niyaz has a tree with $n$ vertices numerated from $1$ to $n$. A tree is a connected graph without cycles.

Each edge in this tree has strictly positive integer weight. A degree of a vertex is the number of edges adjacent to this vertex.

Niyaz does not like when vertices in the tree have too large degrees. For each $x$ from $0$ to $(n-1)$, he wants to find the smallest total weight of a set of edges to be deleted so that degrees of all vertices become at most $x$.

Input

The first line contains a single integer $n$ ($2 \le n \le 250\,000$) — the number of vertices in Niyaz’s tree.

Each of the next $(n – 1)$ lines contains three integers $a$, $b$, $c$ ($1 \le a, b \le n$, $1 \leq c \leq 10^6$) — the indices of the vertices connected by this edge and its weight, respectively. It is guaranteed that the given edges form a tree.

Output

Print $n$ integers: for each $x = 0, 1, \ldots, (n-1)$ print the smallest total weight of such a set of edges that after one deletes the edges from the set, the degrees of all vertices become less than or equal to $x$.

Examples

input

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

output

10 6 3 1 0 

input

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

output

22 6 0 0 0 

Note

In the first example, the vertex $1$ is connected with all other vertices. So for each $x$ you should delete the $(4-x)$ lightest edges outgoing from vertex $1$, so the answers are $1+2+3+4$, $1+2+3$, $1+2$, $1$ and $0$.

In the second example, for $x=0$ you need to delete all the edges, for $x=1$ you can delete two edges with weights $1$ and $5$, and for $x \geq 2$ it is not necessary to delete edges, so the answers are $1+2+5+14$, $1+5$, $0$, $0$ and $0$.

Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<pair<int, int>>> graph(n);
long long total = 0;
for (int i = 0; i < n - 1; i++) {
    int x, y, z;
    cin >> x >> y >> z;
x--; y--;
graph[x].emplace_back(y, z);
graph[y].emplace_back(x, z);
total += z;
}
vector<vector<int>> at_deg(n);
vector<int> deg(n);
for (int i = 0; i < n; i++) {
    deg[i] = (int) graph[i].size();
    at_deg[deg[i]].push_back(i);
  }
  vector<vector<pair<int, int>>> g(n);
vector<int> alive(n, 0);
vector<multiset<int>> extra_small(n);
vector<multiset<int>> extra_big(n);
vector<long long> sum_extra_big(n, 0);
vector<long long> res(n, 0);
set<int> lovers;
long long saved = total;
vector<int> was(n, -1);
for (int dd = n - 1; dd >= 1; dd--) {
auto BalanceOver = [&](int v) {
while ((int) extra_big[v].size() > dd) {
auto it = extra_big[v].begin();
sum_extra_big[v] -= *it;
extra_small[v].insert(*it);
extra_big[v].erase(it);
}
};
auto BalanceUnder = [&](int v) {
while ((int) extra_big[v].size() < dd && !extra_small[v].empty()) {
        auto it = prev(extra_small[v].end());
        sum_extra_big[v] += *it;
        extra_big[v].insert(*it);
        extra_small[v].erase(it);
      }
    };
    auto Add = [&](int x, int y) {
      extra_big[x].insert(y);
      sum_extra_big[x] += y;
      BalanceOver(x);
    };
    auto Remove = [&](int x, int y) {
      auto it = extra_small[x].find(y);
      if (it != extra_small[x].end()) {
        extra_small[x].erase(it);
      } else {
        it = extra_big[x].find(y);
        assert(it != extra_big[x].end());
        extra_big[x].erase(it);
        sum_extra_big[x] -= y;
        BalanceUnder(x);
      }
    };
    for (int v : lovers) {
      BalanceOver(v);
    }
    function<pair<long long, long long>(int, int)> dfs = [&](int v, int pr) -> pair<long long, long long> {
was[v] = dd;
vector<long long> saveable;
long long overall = 0;
long long total_saveable = 0;
int up_cost = 0;
for (auto& p : g[v]) {
int to = p.first;
int cost = p.second;
if (to == pr) {
up_cost = cost;
continue;
}
auto z = dfs(to, v);
overall += z.first;
if (z.second > z.first) {
saveable.push_back(z.second - z.first);
total_saveable += z.second - z.first;
}
}
sort(saveable.begin(), saveable.end());
int cnt = (int) saveable.size() + (int) extra_big[v].size();
long long val = overall + total_saveable + sum_extra_big[v];
int i = 0;
auto it = extra_big[v].begin();
long long tmp0 = -1;
long long tmp1 = -1;
for (int rot = 0; rot < 2; rot++) {
        while (cnt > dd - rot) {
if (it == extra_big[v].end() || (i < (int) saveable.size() && saveable[i] < *it)) {
            val -= saveable[i];
            ++i;
          } else {
            val -= *it;
            ++it;
          }
          cnt--;
        }
        if (rot == 0) {
          tmp0 = val;
        } else {
          tmp1 = val;
        }
      }
      return make_pair(tmp0, tmp1 + up_cost);
    };
    long long dp = 0;
    for (int v : lovers) {
      if (was[v] == dd) {
        continue;
      }
      auto p = dfs(v, -1);
      dp += p.first;
    }
    res[dd] = total - (saved + dp);
    for (int v : at_deg[dd]) {
      for (auto& p : graph[v]) {
        int u = p.first;
        int cost = p.second;
        if (alive[u]) {
          g[v].emplace_back(u, cost);
          g[u].emplace_back(v, cost);
          Remove(u, cost);
        } else {
          Add(v, cost);
          saved -= cost;
        }
      }
      alive[v] = 1;
      lovers.insert(v);
    }
  }
  res[0] = total;
  for (int i = 0; i < n; i++) {
    if (i > 0) {
cout << " ";
    }
    cout << res[i];
  }
  cout << '\n';
  return 0;
}