//chockolateman
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
int K,par[2005],par_w[2005],deg[2005],depth[2005],jump[2005],jumpdeg[2005],need[2005];
long long dp[2005][2005][2];
vector<pair<int,int>> adj[2005];
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];
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;
int w = e.second;
if(u != p)
dfs2(u,v);
}
dp[v][0][1] = INF;
for(int k = 0 ; k <= need[v] ; k++)
{
if(k)
dp[v][k][1] = 0;
dp[v][k][0] = par_w[v];
vector<int> temp;
for(auto e : adj[v])
{
int u = e.first;
if(u != p)
{
if(dp[u][k][0]==0)
dp[u][k][0] = par_w[u];
dp[v][k][0] += dp[u][k][0];
dp[v][k][1] += dp[u][k][0];
temp.push_back(dp[u][k][0] - dp[u][k][1]);
}
}
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[v][k][0] -= temp[i];
dp[v][k][1] -= temp[i];
}
if(k > 0 && L >= k && temp[k-1] > 0)
dp[v][k][0] -= temp[k-1];
int nxt = find_nxt(v,k-1);
if(nxt != v)
{
if(dp[nxt][k][0]==0)
dp[nxt][k][0] = par_w[nxt];
dp[nxt][k][0] += min(dp[v][k][0],dp[v][k][1]);
dp[nxt][k][1] += min(dp[v][k][0],dp[v][k][1]);
}
}
}
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[1][k][0]);
return ret;
}
