/*input
6
0 1 915391369
0 2 237972545
0 3 329957228
1 4 112014910
3 5 69344110
*/
#include "roads.h"
#include "roads.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
const int maxn=2e5+5;
#define sz(x) (int)x.size()
#define MNTO(x,y) x=min(x,(__typeof(x))y)
#define pb push_back
const int INF=0x3f3f3f3f;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
set<pii> v[maxn];
ll dp[maxn][2];
int vis[maxn];
struct MS{
int k;
multiset<ll> small,big;
ll sum=0;
void bal(){
while(sz(big) and sz(small)<k and (*big.begin())<0){
sum+=(*big.begin());
small.insert(*big.begin());
big.erase(big.begin());
}
while(sz(small) and sz(small)>k){
sum-=(*prev(small.end()));
big.insert((*prev(small.end())));
small.erase(prev(small.end()));
}
}
void add(ll x){
big.insert(x);
if(sz(small) and (*prev(small.end()))>(*big.begin())){
ll a=(*big.begin()),b=(*prev(small.end()));
sum+=a-b;
big.erase(big.begin());
small.erase(prev(small.end()));
big.insert(b),small.insert(a);
}
}
void del(ll x){
if(small.find(x)!=small.end()){
sum-=x;
small.erase(small.find(x));
}
else{
big.erase(big.find(x));
}
}
};
int k;
MS ms[maxn];
ll tot[maxn];
inline void dfs(int u,int p){
vis[u]=k;
vector<ll> vv;
ll ans=tot[u];
for(auto x:v[u]){
if(x.f==p) continue;
dfs(x.f,u);
ll z=dp[x.f][0]-dp[x.f][1]-x.s;
ms[u].add(z);
ans+=dp[x.f][1]+x.s;
vv.pb(z);
}
ms[u].k=k-1;
ms[u].bal();
dp[u][0]=ans+ms[u].sum;
ms[u].k=k;
ms[u].bal();
dp[u][1]=ans+ms[u].sum;
// cout<<ms[u].sum<<'\n';
// for(auto x:ms[u].small) cout<<x<<' ';
//cout<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n';
for(auto x:vv) ms[u].del(x);
}
std::vector<long long> minimum_closure_costs(int N, vector<int> U,vector<int> V,vector<int> W) {
int n=N;
vector<pii> vv;
REP(i,n-1){
v[U[i]].insert({V[i],W[i]});
v[V[i]].insert({U[i],W[i]});
}
REP(i,n) vv.pb({sz(v[i]),i}),vis[i]=-1;
sort(ALL(vv));
reverse(ALL(vv));
vector<ll> ans(n);
REP(i,n){
k=i;
while(sz(vv) and vv.back().f<=i){
int z=vv.back().s;
for(auto x:v[z]){
tot[x.f]+=x.s;
ms[x.f].add(-x.s);
v[x.f].erase({z,x.s});
//cout<<i<<' '<<x.f<<' '<<x.s<<'\n';
}
vv.pop_back();
}
for(auto x:vv){
ms[x.s].k=i-1;
}
for(auto x:vv){
if(vis[x.s]!=k){
dfs(x.s,-1);
ans[i]+=dp[x.s][1];
}
}
//REP(j,n) cout<<j<<' '<<dp[j][0]<<' '<<dp[j][1]<<'\n';
}
return ans;
}
