#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(c) c.begin(), c.end()
#define endl "\n"
const double PI=3.141592653589;
void __print(ll x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
#include <vector>
/*
dp[i][j][0] min cost to delete edges such that each node in the subtree of node i has atmost j active edges and the edge from (par[i],i) is still active
let's say node i has k edges from it(including parent), if parent is still active then we need to delete to delete k-j down edges otherwise if we are kiling parent edge then k-j-1 down edges to be deleted.
cost of deleting edge from u->v is min(dp[v][j][1],dp[v][j][0]+w[u,v]-jth costliest edge of v)
cost of keeping edge u->v is min(dp[v][j][0],dp[v][j][1])
sort by decreasing order of keeping-deleting cost and delete the first x
*/
vector<vector<vector<ll>>>dp;
vector<vector<pair<ll,ll>>>adj;
vector<vector<ll>>other;
ll n;
vector<ll>par;
void dfs(ll u, ll p){
for(auto &[w,v] : adj[u]){
if(v==p)continue;
dfs(v,u);
}
for(ll j = 0;j<n;++j){
vector<pair<ll,ll>>val;
for(auto &[w,v] : adj[u]){
if(v==p)continue;
val.pb({min(dp[v][j][0],dp[v][j][1]),dp[v][j][1]});
}
ll x = adj[u].size()-j;
sort(all(val), [&](auto one,auto two){
return one.first-one.second > two.first - two.second;
});
if(u==0){
for(ll i = 0;i<min((ll)val.size(),x);++i)dp[u][j][0]+=val[i].second;
for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first;
}else if(j>0){
for(ll i = 0;i<min((ll)val.size(),x);++i)dp[u][j][0]+=val[i].second;
for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][0] += val[i].first;
}
x--;
for(ll i = 0;i<min((ll)val.size(),x);++i)dp[u][j][1]+=val[i].second;
for(ll i = max(0ll,x);i<val.size();++i)dp[u][j][1] += val[i].first;
}
}
void comp(ll u, ll p){
for(auto &[w,v] : adj[u]){
if(v==p)continue;
par[v] = u;
for(ll j = 0;j<n;++j)dp[v][j][1] = w;
comp(v,u);
}
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
n = N;
dp = vector<vector<vector<ll>>>(n+1, vector<vector<ll>>(n+1,vector<ll>(2)));
adj.resize(n+1);
par.resize(n+1);
other.resize(n+1);
for(ll i = 0;i<n-1;++i)adj[U[i]].pb({W[i],V[i]}),adj[V[i]].pb({W[i],U[i]});
comp(0,-1);
for(ll i = 0;i<n;++i){
for(auto &[w,v] : adj[i]){
if(v==par[i])continue;
other[i].pb(w);
}
sort(all(other[i]));
sort(all(adj[i]));
}
for(ll i = 1;i<n;++i)dp[i][0][0] = 1e18;
comp(0,-1);
dfs(0,-1);
vector<ll>res;
for(ll i = 0;i<n;++i)res.pb(dp[0][i][0]);
return res;
}
