#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
#include "roads.h"
//#include "grader.cpp"
vector<ll>minimum_closure_costs(int N,vector<int>U,vector<int>V,vector<int>W){
	bool star=1,chain=1,unweighted=1;
	for(int i=0;i<N-1;i++)star&=(U[i]==0),chain&=(U[i]==i&&V[i]==i+1),unweighted&=(W[i]==1);
	if(star){
		sort(W.begin(),W.end(),greater<int>());
		vector<ll>res;
		for(auto x:W)res.push_back(x);
		res.push_back(0);
		for(int i=N-2;i>=0;i--)res[i]+=res[i+1];
		return res;
	}
	if(chain){
		vector<ll>res(N);
		res[0]=accumulate(W.begin(),W.end(),0LL);
		ll cur=0,lst=0;
		for(int i=0;i<W.size();i++){
			swap(cur,lst);
			cur=max(cur+W[i],lst);
		}
		res[1]=res[0]-cur;
		return res;
	}
	if(unweighted){
		vector<ll>res(N);
		vector<vector<int>>adj(N);
		for(int i=0;i<N-1;i++){
			adj[U[i]].push_back(V[i]);
			adj[V[i]].push_back(U[i]);
		}
		vector<int>order(N),vis(N),deg(N);
		iota(order.begin(),order.end(),0);
		sort(order.begin(),order.end(),[&](int i,int j){return adj[i].size()>adj[j].size();});
		for(int i=0;i<N;i++)sort(adj[i].begin(),adj[i].end(),[&](int j,int k){return adj[j].size()>adj[k].size();});
		res[0]=N-1;
		for(int k=1;k<N;k++){
			for(auto v:order){
				deg[v]=adj[v].size();
				vis[v]=0;
				if(deg[v]<=k)break;
			}
			function<void(int,int)>dfs=[&](int v,int p){
				vis[v]=1;
				for(auto u:adj[v]){
					if(adj[u].size()<=k)break;
					if(u==p)continue;
					dfs(u,v);
				}
				res[k]+=max(0,deg[v]-k);
				if(deg[v]>k)deg[p]--;
			};
			for(auto v:order){
				if(adj[v].size()<=k)break;
				if(!vis[v])dfs(v,v);
			}
		}
		return res;
	}
	vector<vector<pair<int,int>>>adj(N);
	vector<ll>res(N);
	for(int i=0;i<N-1;i++){
		adj[U[i]].push_back({V[i],W[i]});
		adj[V[i]].push_back({U[i],W[i]});
		res[0]+=W[i];
	}
	vector<vector<ll>>dp(N,{0,0});
	function<void(int,int,int)>dfs=[&](int v,int p,int k){
		vector<ll>vals;
		ll ans=0;
		for(auto[u,w]:adj[v]){
			if(u==p)continue;
			dfs(u,v,k);
			ans+=dp[u][0]+w;
			vals.push_back(dp[u][1]-dp[u][0]-w);
		}
		sort(vals.begin(),vals.end());
		dp[v][0]=dp[v][1]=ans;
		for(int i=0;i<min(k,(int)vals.size());i++){
			ans+=vals[i];
			if(i+1<k)dp[v][1]=min(dp[v][1],ans);
			dp[v][0]=min(dp[v][0],ans);
		}
	};
	for(int i=1;i<N;i++){
		dfs(0,0,i);
		res[i]=dp[0][0];
	}
	return res;
}