typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include "roads.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=200000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
struct Seg{
int n;
vector<ll>sum,arr;
vector<int>cnt;
void build(int node=1,int left=0,int right=-1){
if(right==-1)right=n-1;
if(left==right){
sum[node]=arr[left];
cnt[node]=!!arr[left];
return;
}
build(node*2,left,mid);build(node*2+1,mid+1,right);
sum[node]=sum[node*2]+sum[node*2+1];
cnt[node]=cnt[node*2]+cnt[node*2+1];
}
void launch(){
n=arr.size();
sum.resize(n<<2);
cnt.resize(n<<2);
build();
}
int l,r;
void up(int node=1,int left=0,int right=-1){
if(right==-1)right=n-1;
if(left==right){
sum[node]=r;
cnt[node]=!!r;
return;
}
if(l>mid)up(node*2+1,mid+1,right);
else up(node*2,left,mid);
sum[node]=sum[node*2]+sum[node*2+1];
cnt[node]=cnt[node*2]+cnt[node*2+1];
}
void update(int tar,int x){
l=tar;r=x;
up();
}
ll qu(int node=1,int left=0,int right=-1){
if(right==-1)right=n-1;
if(l==0)return 0;
if(left==right){
return sum[node];
}
if(cnt[node*2]>l)return qu(node*2,left,mid);
l-=cnt[node*2];
return sum[node*2]+qu(node*2+1,mid+1,right);
}
ll query(int x){
l=x;
if(l>cnt[1])return inf;
return qu();
}
};
int n;
int vis[100000];
ll dp[100000][2];
Seg seg[100000];
vector<pair<int,int>>adj[100000],act[100000];
map<int,int>ord[100000];
vector<int>deg[100000],awake;
vector<ll>ans;
void dfs(int pos,int par,int k){
vis[pos]=k;
ll sum=0;
vector<ll>v;
ll parcos=inf;
for(pair<int,int>x:act[pos]){
if(x.fr==par){
parcos=x.sc;
continue;
}
dfs(x.fr,pos,k);
sum+=dp[x.fr][0];
v.pb(dp[x.fr][1]-dp[x.fr][0]);
}
sort(v.begin(),v.end());
dp[pos][1]=inf;
dp[pos][0]=inf;
dp[pos][1]=min(dp[pos][1],sum+seg[pos].query(max(0,int(adj[pos].size())-k-1))+parcos);
dp[pos][0]=min(min(dp[pos][0],dp[pos][1]),sum+seg[pos].query(max(0,int(adj[pos].size())-k)));
for(int i=0;i<v.size();i++){
sum+=v[i];
dp[pos][1]=min(dp[pos][1],sum+seg[pos].query(max(0,int(adj[pos].size())-i-k-2))+parcos);
dp[pos][0]=min(min(dp[pos][0],dp[pos][1]),sum+seg[pos].query(max(0,int(adj[pos].size())-i-k-1)));
}
}
void wake(int tar){
awake.pb(tar);
for(pair<int,int>x:adj[tar]){
act[x.fr].pb({tar,x.sc});
seg[x.fr].update(ord[x.fr][tar],0);
}
}
vector<ll> minimum_closure_costs(int N,vector<int>U,vector<int>V,vector<int>W){
n=N;
ans.resize(n,0);
for(int i=0;i<n-1;i++){
adj[U[i]].pb({V[i],W[i]});
adj[V[i]].pb({U[i],W[i]});
}
for(int i=0;i<n;i++){
vis[i]=n;
deg[adj[i].size()-1].pb(i);
sort(adj[i].begin(),adj[i].end(),[&](const pair<int,int>&x,const pair<int,int>&y){return x.sc<y.sc;});
for(int j=0;j<adj[i].size();j++){
ord[i][adj[i][j].fr]=j;
seg[i].arr.pb(adj[i][j].sc);
}
seg[i].launch();
}
for(int i=n-1;i>=0;i--){
for(int x:deg[i]){
wake(x);
}
for(int j:awake){
if(vis[j]==i)continue;
dfs(j,-1,i);
ans[i]+=dp[j][0];
}
}
return ans;
}
