#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()
vll dp, dp1, deg;
vvp g;
vector<map<ll,ll>> sm;
void dfs(ll cur, ll pr, ll k){
map<ll,ll> pq = sm[cur];
ll cnt=deg[cur]-k-1;
for(auto [i,e]: g[cur]){
if(i!=pr){
dfs(i,cur,k);
dp1[cur]+=dp[i];
if(dp1[i]-dp[i]+e<0){
cnt--;
dp1[cur]+=dp1[i]-dp[i]+e;
}
else pq[dp1[i]-dp[i]+e]++;
}
}
ll dow=0;
for(auto[i,o]:pq){
if(dow==0){
ll t = max<ll>(0,min(cnt, o));
o-=t;
cnt-=t;
dp1[cur]+=i*t;
if(cnt<=0){
dow=1;
cnt++;
dp[cur]=dp1[cur];
}
}
if(dow==1){
ll t = max<ll>(0,min(cnt, o));
o-=t;
cnt-=t;
dp[cur]+=i*t;
if(cnt<=0){
break;
}
}
}
}
std::vector<long long> minimum_closure_costs(int n, vi u, vi v, vi w) {
g = vvp(n);
vll ans(n);
sm = vector<map<ll,ll>>(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][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;
// }
