//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 dp[2][2005][2005];
vector<pair<int,int>> adj[100005];
void dfs1(int v,int p,int p_w)
{
par[v] = p;
par_w[v] = p_w;
depth[v] = depth[p] + 1;
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];
}
need[v] = deg[v];
if(v==1)
need[1] = K;
for(auto e : adj[v])
{
int u = e.first;
int w = e.second;
if(u != p)
{
dfs1(u,v,w);
need[v] = max(need[v],deg[u]);
}
}
}
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)
{
for(auto e : adj[v])
{
int u = e.first;
if(u != p)
dfs2(u,v);
}
dp[1][v][0] = INF;
for(int k = 0 ; k <= need[v] ; k++)
{
if(k)
dp[1][v][k] = 0;
dp[0][v][k] = par_w[v];
vector<long long> temp;
for(auto e : adj[v])
{
int u = e.first;
if(u != p)
{
if(dp[0][u][k]==0)
dp[0][u][k] = par_w[u];
dp[0][v][k] += dp[0][u][k];
dp[1][v][k] += dp[0][u][k];
temp.push_back(dp[0][u][k] - dp[1][u][k]);
}
}
sort(temp.begin(),temp.end(),greater<long long>());
int L = temp.size();
for(int i = 0 ; i < min(L,k-1) ; i++)
if(temp[i] > 0)
{
dp[0][v][k] -= temp[i];
dp[1][v][k] -= temp[i];
}
if(k > 0 && L >= k && temp[k-1] > 0)
dp[0][v][k] -= temp[k-1];
int nxt = find_nxt(v,k);
if(nxt != v)
{
if(dp[0][nxt][k]==0)
dp[0][nxt][k] = par_w[nxt];
dp[0][nxt][k] += min(dp[0][v][k],dp[1][v][k]);
dp[1][nxt][k] += min(dp[0][v][k],dp[1][v][k]);
}
}
for(int k = need[v] + 1 ; k <= K ; k++)
{
dp[0][v][k] = par_w[v];
dp[1][v][k] = 0;
for(auto e : adj[v])
{
int u = e.first;
dp[0][v][k] += dp[1][u][k];
dp[1][v][k] += dp[1][u][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]]++;
}
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;
}
