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