#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
using vi = vector<int>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
struct seg{
multiset<ll> x,y;
ll sm=0;
seg(){}
void ad(ll v){
y.insert(v);
sm += *y.begin();
x.insert(*y.begin());
y.erase(y.begin());
}
void rem(ll v){
if(x.count(v)){sm-=v;x.erase(x.find(v));}
else y.erase(y.find(v));
}
ll que(ll t){
while(x.size()<t){
sm += *y.begin();
x.insert(*y.begin());
y.erase(y.begin());
}
while(x.size()>t){
sm -= *x.rbegin();
y.insert(*x.rbegin());
auto it = x.end();
x.erase(--it);
}
return sm;
}
};
vll dp, dp1, deg;
vvp g;
vector<seg> sm;
void dfs(ll cur, ll pr, ll k){
ll cnt=deg[cur]-k-1;
ll negs=0,negt=0;
for(auto [i,e]: g[cur]){
if(i!=pr){
dfs(i,cur,k);
dp1[cur]+=dp[i];
if(dp1[i]-dp[i]+e<0){
negt++;
negs+=dp1[i]-dp[i]+e;
}
sm[cur].ad(dp1[i]-dp[i]+e);
}
}
dp[cur]=dp1[cur];
if(negt<cnt)dp1[cur] += sm[cur].que(cnt);
else dp1[cur] += negs;
if(negt<cnt+1)dp[cur] += sm[cur].que(cnt+1);
else dp[cur] += negs;
for(auto [i,e]: g[cur]){
if(i!=pr){
sm[cur].rem(dp1[i]-dp[i]+e);
}
}
}
std::vector<long long> minimum_closure_costs(int n, vi u, vi v, vi w) {
g = vvp(n);
vll ans(n);
sm = vector<seg>(n);
deg = vll(n);
for(ll i = 0; i < n-1; ++i){
ans[0]+=w[i];
g[u[i]].pb({v[i],w[i]});
g[v[i]].pb({u[i],w[i]});
deg[u[i]]++;
deg[v[i]]++;
}
vll big;
for(ll i = 0; i < n; ++i){
sort(all(g[i]), [&](pll a, pll b){
if(deg[a.f]>deg[b.f])return 1;
if(deg[a.f]<deg[b.f])return 0;
if(a.s<b.s)return 1;
return 0;
});
big.pb(i);
}
sort(all(big), [&](ll a, ll b){
if(deg[a]>deg[b])return 1;
if(deg[a]<deg[b])return 0;
if(a<b)return 1;
return 0;
});
dp=dp1=vll(n);
for(ll i = 1; i < n; ++i){
while(!big.empty() && deg[big.back()]<=i){
ll c = big.back();
big.pop_back();
for(auto [j,e]: g[c]){
if(deg[j]>i){
g[j].pop_back();
sm[j].ad(e);
}
}
}
for(ll j: big){
dp[j]=-1;
dp1[j]=0;
}
for(ll j: big){
if(dp[j]==-1){dfs(j,j,i);ans[i]+=dp[j];}
}
}
return ans;
}
// int main() {
// int N;
// assert(1 == scanf("%d", &N));
// vi U(N - 1), V(N - 1), W(N - 1);
// for (int i = 0; i < N - 1; ++i) {
// assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
// }
// std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
// for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
// if (i > 0) {
// printf(" ");
// }
// printf("%lld",closure_costs[i]);
// }
// printf("\n");
// return 0;
// }
