#include "roads.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std; 
typedef long long ll;
const ll inf=1e14;
const int N=1e5+99;
ll f[N],g[N],cnt[N];
struct edge{
	int v,w,nxt;
}edg[N*2];
int hd[N],cntedge;
void add(int u,int v,int w){
	cntedge++;
	edg[cntedge]=(edge){v,w,hd[u]};
	hd[u]=cntedge;
}
void dfs(int u,int fa,int res){
	priority_queue<ll> que;
	g[u]=f[u]=0;
	ll v,w;
	for(int i=hd[u];i;i=edg[i].nxt){
		v=edg[i].v; w=edg[i].w;
		if(v==fa) continue;
		dfs(v,u,res);
		f[u]+=f[v]; g[u]+=f[v];
		que.push(-(g[v]+w-f[v]));
	}
	ll now;
	for(int i=1;i<=cnt[u]-res-1;i++){
		now=que.top(); que.pop(); now=-now;
		f[u]+=now; g[u]+=now;
	}
	if(cnt[u]-res>=1){
		if(que.empty()) f[u]=inf;
		else{
			now=que.top(); que.pop(); now=-now;
			f[u]+=now; g[u]+=min(now,0ll);
		}
	};
	while(!que.empty()){
		now=que.top(); que.pop(); now=-now;
		f[u]+=min(now,0ll); g[u]+=min(now,0ll);
	}
	return;
}
std::vector<long long> minimum_closure_costs(int n, std::vector<int> u,
                                             std::vector<int> v,
                                             std::vector<int> w) {
	vector<ll> re;
	re.resize(n);
	int b1=1,b2=1;
    for(int i=0;i<=n-2;i++){
    	if(u[i]!=0) b1=0;
    	if(u[i]!=i||v[i]!=i+1) b2=0;
	}
	if(b1){
		sort(w.begin(),w.end());
		for(int i=n-2;i>=0;i--)
			re[i]=re[i+1]+w[n-2-i];
	}
	else if(b2){
		for(int i=0;i<=n-2;i++) re[0]+=w[i];
		for(int i=1;i<=n-1;i++){
			f[i]=g[i-1];
			g[i]=(ll)w[i-1]+min(g[i-1],f[i-1]);
		}
		re[1]=min(f[n-1],g[n-1]);
	}
	else if(n<=2000){
		for(int i=0;i<=n-2;i++){
			add(u[i],v[i],w[i]); add(v[i],u[i],w[i]);
			cnt[u[i]]++; cnt[v[i]]++; 
		}
		for(int i=0;i<=n-1;i++){
			dfs(0,-1,i);
			re[i]=f[0];
		}
	}
	return re;
}