#pragma GCC optimize("O3")
#include "roads.h"
#include<vector>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
#define MP make_pair
#define F first
#define S second
const int MAXN=100010;
vector<pii> g[MAXN], lim[MAXN];
vector<pair<int, pii>> ar[MAXN];
int vert[MAXN], dep[MAXN], par[MAXN];
bool vis[MAXN];
ll parCost[MAXN];
struct node{
map<int, ll> cost;
set<pli> fst;
set<pli>::iterator itr;
int pos=0;
ll sum=0;
node(int v, int p){
for(auto to:g[v]) if(to.F!=p){
cost[to.F]=to.S;
fst.insert(MP(to.S, to.F));
}
itr=fst.begin();
}
node(){}
void insert(pii pa){
auto it = fst.insert(pa).F;
if(itr==fst.end() || *it<*itr){
itr = prev(itr);
sum+=it->F-itr->F;
}
}
void erase(set<pli>::iterator it){
if(itr==fst.end() || *it<=*itr){
sum+=itr->F-it->F;
itr = next(itr);
}
fst.erase(it);
}
void update(int to, ll value){
ll cst = cost[to];
if(cst==value) return;
auto it = fst.find(MP(cst, to));
insert(MP(value, to));
erase(it);
cost[to]=value;
}
void incr(){
pos++;
sum+=itr->F;
itr=next(itr);
}
ll find_sum(int ind){
while(pos<ind) incr();
return sum;
}
};
int n, stat=0;
node info[MAXN];
void dfs_cons(int v, int p){
for(auto to:g[v]) if(to.F!=p){
par[to.F]=v;
parCost[to.F]=to.S;
dep[to.F]=dep[v]+1;
info[v] = node(v, p);
dfs_cons(to.F, v);
}
}
ll dfs(int v, int p){
vis[v]=true;
ll base=0;
int extra = g[v].size()-stat;
for(auto to:lim[v]) if(to.F!=p){
base+=dfs(to.F, v);
}
ll ex1=(v? (info[v].find_sum(max(extra-1, 0)) + parCost[v]) : 1000000000000000000);
ll ex2=info[v].find_sum(extra);
base+=min(ex1, ex2);
ll add = max(0LL, ex1-ex2);
if(v) info[p].update(v, add);
return base;
}
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
vector<ll> res(N, 0);
n=N;
forn(i, n-1){
g[U[i]].PB({V[i], W[i]});
g[V[i]].PB({U[i], W[i]});
res[0]+=W[i];
}
dfs_cons(0, 0);
forn(i, n) vert[i]=i;
sort(vert, vert+n, [](int a, int b){
return (g[a].size()!=g[b].size()? g[a].size()>g[b].size() : dep[a]<dep[b]);
});
forn(i, n-1){
int u=U[i], v=V[i], w=W[i];
int d = min(g[u].size(), g[v].size());
ar[d].PB(MP(u, MP(v, w)));
}
dforsn(i, 1, n){
stat=i;
for(auto edge:ar[i]){
lim[edge.F].PB(MP(edge.S.F, edge.S.S));
lim[edge.S.F].PB(MP(edge.F, edge.S.S));
}
for(int j=0; j<n && g[vert[j]].size()>=i; ++j){
int v = vert[j];
if(!vis[v]){
res[i]+=dfs(v, par[v]);
}
}
for(int j=0; j<n && g[vert[j]].size()>=i; ++j) vis[vert[j]]=false;
}
return res;
}
