#include "roads.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=2e3+10;
mt19937 mt(time(NULL));
struct node{
int sz,val,pri,sum;
node *l,*r;
};
node *init(int key){
node *t=new node;
*t={1,key,(int)mt(),key,0,0};
return t;
}
int sz(node *t){if(!t) return 0; return t->sz;}
ll fs(node *t){if(!t) return 0; return t->sum;}
void upd(node *t){
if(!t) return;
t->sz=1+sz(t->l)+sz(t->r);
t->sum=t->val+fs(t->l)+fs(t->r);
}
void splitv(node *t,node *&l,node *&r,int k){
if(!t) return void(l=r=NULL);
if(t->val<=k) splitv(t->r,t->r,r,k),l=t;
else splitv(t->l,l,t->l,k),r=t;
upd(t);
}
void splits(node *t,node *&l,node *&r,int k){
if(!t) return void(l=r=NULL);
if(k-sz(t->l)-1>=0) splits(t->r,t->r,r,k-sz(t->l)-1),l=t;
else splits(t->l,l,t->l,k),r=t;
upd(t);
}
void merge(node *&t,node *l,node *r){
if(!l) return void(t=r);
if(!r) return void(t=l);
if(l->pri>r->pri) merge(l->r,l->r,r),t=l;
else merge(r->l,l,r->l),t=r;
upd(t);
}
ll query(node *t,int k){
if(k>sz(t)) return (ll)(1e15);
node *l,*r;
splits(t,l,r,k);
ll ret=fs(l);
merge(t,l,r);
return ret;
}
node *uwu[M];
int n,deg[M],ti,bd,dep[M];
int vs[M];
set<pair<int,ll>> adj[M],act;
vector<int> del[M];
ll dp[M][2];
void dfs(int u,int p,ll w=0){
vs[u]=ti;
dp[u][0]=dp[u][1]=0;
priority_queue<ll,vector<ll>,greater<ll>> q;
int cnt=0;
for(auto [v,wn]:adj[u]){
if(v==p) continue;
dfs(v,u,wn);
dp[u][0]+=dp[v][0];
dp[u][1]+=dp[v][0];
q.push({dp[v][1]-dp[v][0]});
cnt++;
}
int m=deg[u]-(int)(adj[u].size());
int pi=deg[u]-bd;
//cout<<"u ";
//cout<<u <<" " <<m <<" " <<pi <<"\n";
ll add=1e15,base=0,add2=1e15;
for(int i=0;i<=pi;i++){
//cout<<"i" <<i <<"\n";
//pick more pi-i from treap!!
if(pi-i<=m){
add=min(add,query(uwu[u],pi-i)+base);
}
if(pi-i-1<=m && i!=pi){
add2=min(add2,query(uwu[u],pi-i-1)+base);
}
//cout<<query(uwu[u],pi-i) <<" " <<base <<"\n";
if(q.empty()) break;
base+=q.top();
q.pop();
}
dp[u][0]+=add;
dp[u][1]+=add2+w;
dp[u][0]=min(dp[u][0],(ll)(1e15));
dp[u][1]=min(dp[u][1],(ll)(1e15));
//cout<<"end" <<dp[u][0] <<" " <<dp[u][1] <<"\n";
}
std::vector<long long> minimum_closure_costs(int N, vector<int> U,vector<int> V,vector<int> W) {
n=N;
vector<ll> ret(N,0);
ll sum=0;
set<int> act;
for(int i=0;i<N-1;i++){
adj[U[i]].insert({V[i],W[i]});
adj[V[i]].insert({U[i],W[i]});
deg[U[i]]++,deg[V[i]]++;
}
for(int i=0;i<N;i++){
del[adj[i].size()].push_back(i);
act.insert(i);
uwu[i]=0;
}
for(int i=0;i<N;i++){
bd=i;
for(auto x:del[i]){
act.erase(x);
for(auto [v,w]:adj[x]){
adj[v].erase({x,w});
node *l,*r,*tmp;
tmp=init(w);
splitv(uwu[v],l,r,w);
merge(l,l,tmp);
merge(uwu[v],l,r);
}
}
//cout<<"PRO" <<i <<"\n";
//for(auto u:act) cout<<u <<" ";
//cout<<"\n";
ti++;
//solve
for(auto u:act){
if(vs[u]!=ti){
dfs(u,u);
ret[i]+=dp[u][0];
//cout<<"ret" <<u <<" " <<dp[u][0] <<"\n";
}
}
}
return ret;
}
