#include "roads.h"
#include <bits/stdc++.h>
#define REP(i,o,n) for(long long i=o;i<n;i++)
#define fi first
#define se second
#define pb push_back
using namespace std;
vector<pair<long long,long long>> adj[200100];
vector<pair<long long,long long>> child[200100];
long long sz[200100];
long long memo[2010][2010][2];
void dfs(long long node, long long parent=-1){
sz[node]=1;
for(auto i:adj[node]){
if(i.fi!=parent)dfs(i.fi,node),sz[node]+=sz[i.fi],child[node].pb(i);
}
}
long long dp(long long node, long long k, bool lim){
auto &ans=memo[node][k][lim];
if(ans!=-1)return ans;
ans=0;
long long con=k;
if(lim)con--;
con=max(con,0LL);
vector<long long> upgrades;
for(auto i:child[node]){
ans+=dp(i.fi,k,false)+i.se;
upgrades.pb(dp(i.fi,k,true) - (dp(i.fi,k,false)+i.se));
}
sort(upgrades.begin(),upgrades.end());
REP(i,0,con){
if(upgrades.size()>i && upgrades[i]<0)ans+=upgrades[i];
}
return ans;
}
std::vector<long long> minimum_closure_costs(signed N, std::vector<signed> U,
std::vector<signed> V,
std::vector<signed> W) {
memset(sz,-1,sizeof sz);
REP(i,0,N)adj[i].clear();
REP(i,0,N-1){
adj[U[i]].pb({V[i],W[i]});
adj[V[i]].pb({U[i],W[i]});
}
dfs(0);
memset(memo,-1,sizeof memo);
vector<long long> vec;
REP(i,0,N)vec.pb(dp(0,i,false));
return vec;
}
