//chockolateman
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
int K,par[100005],par_w[100005],deg[100005],depth[100005],jump[100005],jumpdeg[100005],need[100005];
long long removing,penalty;
map<int,long long> dp[2][100005];
vector<pair<int,int>> adj[100005];
vector<multiset<long long>> diffs[100005];
multiset<long long> active;
multiset<long long> inactive;
void dfs1(int v,int p,int p_w)
{
par[v] = p;
par_w[v] = p_w;
depth[v] = depth[p] + 1;
need[v] = deg[v];
for(auto e : adj[v])
{
int u = e.first;
if(u != p)
need[v] = max(need[v],deg[u]);
}
if(v==1)
need[1] = K;
if(depth[jump[p]] - depth[jump[jump[p]]] == depth[p] - depth[jump[p]])
{
jump[v] = jump[jump[p]];
jumpdeg[v] = max({need[p],jumpdeg[p],jumpdeg[jump[p]]});
}
else
{
jump[v] = p;
jumpdeg[v] = need[p];
}
for(auto e : adj[v])
{
int u = e.first;
int w = e.second;
if(u != p)
dfs1(u,v,w);
}
}
int find_nxt(int v,int k) //gives nxt nde whose par has weight >= k or root if it does not exist
{
while(v != 1 && need[par[v]] < k)
{
if(jumpdeg[v] < k)
v = jump[v];
else
v = par[v];
}
return v;
}
void reset(int k)
{
while(active.size() < k && !inactive.empty())
{
long long cur = *inactive.rbegin();
inactive.erase(inactive.find(cur));
active.insert(cur);
removing += cur;
}
while(!active.empty() && !inactive.empty() && *active.begin() < *inactive.rbegin())
{
long long cur = *active.begin();
active.erase(active.find(cur));
inactive.insert(cur);
removing -= cur;
cur = *inactive.rbegin();
inactive.erase(inactive.find(cur));
active.insert(cur);
removing += cur;
}
}
void add(long long val,int k)
{
inactive.insert(val);
reset(k);
}
void remove(long long val,int k)
{
if(*active.begin() <= val)
{
active.erase(active.find(val));
removing -= val;
}
else
inactive.erase(inactive.find(val));
reset(k);
}
void dfs2(int v,int p)
{
diffs[v].resize(need[v]+1);
vector<pair<int,int>> nodes;
for(auto e : adj[v])
{
int u = e.first;
if(u != p)
{
dfs2(u,v);
nodes.push_back({need[u],u});
}
}
sort(nodes.begin(),nodes.end(),greater<pair<int,int>>());
dp[1][v][0] = INF;
int prv_l = nodes.size();
for(int k = 0 ; k <= need[v] ; k++)
{
dp[0][v][k] += par_w[v];
int l = prv_l;
for(int x = 0 ; x < l ; x++)
{
int cur = nodes[x].first;
int u = nodes[x].second;
if(cur >= k)
{
dp[0][v][k] += dp[0][u][k];
dp[1][v][k] += dp[0][u][k];
if(dp[0][u][k] - dp[1][u][k] > 0)
{
diffs[v][k].insert(dp[0][u][k] - dp[1][u][k]);
add(dp[0][u][k] - dp[1][u][k],k);
}
}
else
{
l = x;
break;
dp[0][v][k] += par_w[u];
dp[1][v][k] += par_w[u];
diffs[v][k].insert(par_w[u]);
}
}
for(int x = l ; x < prv_l ; x++)
{
int u = nodes[x].second;
penalty += par_w[u];
add(par_w[u],k);
}
reset(k);
dp[0][v][k] += penalty - removing;
dp[1][v][k] += penalty - removing;
if(k > 0 && active.size()==k)
dp[1][v][k] += *active.begin();
for(int x = 0 ; x < l ; x++)
{
int cur = nodes[x].first;
int u = nodes[x].second;
if(dp[0][u][k] - dp[1][u][k] > 0)
{
diffs[v][k].insert(dp[0][u][k] - dp[1][u][k]);
remove(dp[0][u][k] - dp[1][u][k],k);
}
}
prv_l = l;
int nxt = find_nxt(v,k);
if(nxt != v)
{
dp[0][par[nxt]][k] += min(dp[0][v][k],dp[1][v][k]);
dp[1][par[nxt]][k] += min(dp[0][v][k],dp[1][v][k]);
}
}
active.clear();
inactive.clear();
removing = 0;
penalty = 0;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,std::vector<int> V, std::vector<int> W)
{
K = N;
for(int i = 0 ; i < N-1 ; i++)
{
U[i]++;
V[i]++;
adj[U[i]].push_back({V[i],W[i]});
adj[V[i]].push_back({U[i],W[i]});
deg[U[i]]++;
deg[V[i]]++;
}
jump[1] = 1;
dfs1(1,1,0);
dfs2(1,1);
vector<long long> ret;
for(int k = 0 ; k < K ; k++)
ret.push_back(dp[0][1][k]);
return ret;
}
