#include <bits/stdc++.h>   using namespace std;   struct edge_t {     int u, dist;   };   struct firstk_sum_t {     multiset<long long> left, right;     long long left_sum = 0LL;     void insert(long long value) {       if (!left.empty() && value <= *left.rbegin()) {         left.insert(value);         left_sum += value;       } else {         right.insert(value);       }     }     void erase(long long value) {       if (!left.empty() && value <= *left.rbegin()) {         auto it = left.find(value);         if (it != left.end()) {           left_sum -= *it;           left.erase(it);         }       } else {         auto it = right.find(value);         if (it != right.end()) right.erase(it);       }     }     long long get_sum(int k) {       while (!left.empty() && (int)left.size() > k) {         auto it = left.end();         --it;         right.insert(*it);         left_sum -= *it;         left.erase(it);       }       while (!right.empty() && (int)left.size() < k) {         auto it = right.begin();         left.insert(*it);         left_sum += *it;         right.erase(it);       }       return left_sum;     }   };   struct res_t {     int parent_cost;     vector<long long> with;     vector<long long> without_override;     res_t *dup_prefix(int size) {       res_t *result = new res_t;       result->parent_cost = parent_cost;       result->with = vector<long long>(           with.begin(), with.begin() + min(size, (int)with.size()));       result->without_override = vector<long long>(           without_override.begin(),           without_override.begin() + min(size, (int)without_override.size()));       return result;     }     void set_without(int i, long long value) {       int new_size = i + 1;       without_override.reserve(new_size);       while ((int)without_override.size() < new_size) {         without_override.push_back(with[without_override.size()]);       }       without_override[i] = value;     }     long long get_with(int i) {       if (i < (int)with.size())         return with[i];       else         return 0LL;     }     long long get_without(int i) {       if (i < (int)without_override.size())         return without_override[i];       else if (i < (int)with.size())         return with[i];       else         return 0LL;     }   };   res_t *solve(int v, int p, int pc, const vector<vector<edge_t>> &adj) {     vector<res_t *> children;     for (const edge_t &ed : adj[v])       if (ed.u != p) children.push_back(solve(ed.u, v, ed.dist, adj));     if (children.empty()) {       res_t *result = new res_t;       result->parent_cost = pc;       result->with = {LLONG_MAX};       result->without_override = {0LL};       return result;     } else {       sort(children.begin(), children.end(),            [](const res_t *lhs, const res_t *rhs) {              return lhs->with.size() > rhs->with.size();            });       int compute_until = (int)children.size() + 2;       if ((int)children.size() >= 2)         compute_until = max(compute_until, (int)children[1]->with.size());       res_t *children0start = children[0]->dup_prefix(compute_until);       res_t *result = children[0];       children[0] = children0start;       firstk_sum_t first_k;       vector<long long> children_value(children.size());       int good_to_remove = 0;       for (int i = 0; i < (int)children.size(); ++i) {         children_value[i] = children[i]->parent_cost;         good_to_remove += (children_value[i] < 0);         first_k.insert(children_value[i]);       }       result->with.resize(max((int)result->with.size(), compute_until));       result->with[0] = LLONG_MAX;       for (int j = compute_until - 1; j >= 1; --j) {         result->with[j] = 0LL;         for (int i = 0; i < (int)children.size(); ++i) {           if ((int)children[i]->with.size() <= j) break;           result->with[j] += children[i]->get_with(j);         }         int max_children = j - 1;         int nremove = (int)children.size() - max_children;         for (int i = 0; i < (int)children.size(); ++i) {           if ((int)children[i]->with.size() <= j) break;           first_k.erase(children_value[i]);           good_to_remove -= (children_value[i] < 0);           children_value[i] = children[i]->get_without(j) -                               children[i]->get_with(j) + children[i]->parent_cost;           good_to_remove += (children_value[i] < 0);           first_k.insert(children_value[i]);         }         nremove = max(nremove, good_to_remove);         long long total_cost = first_k.get_sum(nremove);         result->with[j] += total_cost;       }       result->without_override.clear();       first_k.left.clear();       first_k.right.clear();       first_k.left_sum = 0LL;       good_to_remove = 0;       for (int i = 0; i < (int)children.size(); ++i) {         children_value[i] = children[i]->parent_cost;         good_to_remove += (children_value[i] < 0);         first_k.insert(children_value[i]);       }       long long without0 = 0LL;       for (int i = 0; i < (int)children.size(); ++i) {         without0 += children[i]->get_without(0);         without0 += children[i]->parent_cost;       }       result->set_without(0, without0);       for (int j = compute_until - 1; j >= 1; --j) {         long long children_cost = 0LL;         for (int i = 0; i < (int)children.size(); ++i) {           if ((int)children[i]->with.size() <= j) break;           children_cost += children[i]->get_with(j);         }         int max_children = j;         int nremove = (int)children.size() - max_children;         for (int i = 0; i < (int)children.size(); ++i) {           if ((int)children[i]->with.size() <= j) break;           first_k.erase(children_value[i]);           good_to_remove -= (children_value[i] < 0);           children_value[i] = children[i]->get_without(j) -                               children[i]->get_with(j) + children[i]->parent_cost;           good_to_remove += (children_value[i] < 0);           first_k.insert(children_value[i]);         }         nremove = max(nremove, good_to_remove);         long long total_cost = first_k.get_sum(nremove);         result->set_without(j, children_cost + total_cost);       }       if (pc != INT_MAX) {         for (int j = 1; j < compute_until; ++j) {           result->with[j] =               min(result->with[j], result->without_override[j] + pc);         }       }       result->parent_cost = pc;       return result;     }   }   int main() {     int n;     scanf( %d , &n);     vector<vector<edge_t>> adj(n);     for (int i = 0; i < n - 1; ++i) {       int a, b, c;       scanf( %d %d %d , &a, &b, &c), --a, --b;       adj[a].push_back({b, c});       adj[b].push_back({a, c});     }     res_t *result = solve(0, -1, INT_MAX, adj);     for (int i = 0; i < n; ++i) {       if (i > 0) printf(   );       printf( %lld , result->get_without(i));     }     printf(  n );     return 0;   }   