//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];
map<int,long long> dp[2][100005];
vector<pair<int,int>> adj[100005];
vector<multiset<long long>> diffs[100005];
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 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;
for(int k = 0 ; k <= need[v] ; k++)
{
dp[0][v][k] += par_w[v];
for(auto x : nodes)
{
int cur = x.first;
int u = 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]);
}
else
{
dp[0][v][k] += par_w[u];
dp[1][v][k] += par_w[u];
diffs[v][k].insert(par_w[u]);
}
}
int cnt = 0;
while(cnt < k && !diffs[v][k].empty())
{
cnt++;
long long cur = *diffs[v][k].rbegin();
diffs[v][k].erase(diffs[v][k].find(cur));
dp[0][v][k] -= cur;
if(cnt != k)
dp[1][v][k] -= cur;
}
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]);
}
}
}
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;
}
