#include<bits/stdc++.h>
#include "roads.h"
#include <vector>
#define ll long long
using namespace std;
const ll N = 2010;
const ll inf = 1e18/N;
vector <pair<ll, ll>> g[N];
ll dp[N][N][2];
void solve(ll p, ll v, ll k, ll fg){
if(dp[v][k][fg] != -1) return;
ll sum = 0;
vector <ll> best;
for(auto [x, w] : g[v]){
if(x == p) continue;
solve(v, x, k, 0);
solve(v, x, k, 1);
sum += dp[x][k][0];
best.push_back(dp[x][k][1]-dp[x][k][0]+w);
}
ll deg = g[v].size();
deg -= fg;
sort(best.begin(), best.end());
reverse(best.begin(), best.end());
while(deg > k or (!best.empty() ? best.back() <= 0 : false)){
if(best.empty()) break;
sum += best.back();
deg--;
best.pop_back();
}
dp[v][k][fg] = (deg > k ? inf : sum);
return;
}
vector<long long> minimum_closure_costs(int n, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
memset(dp, -1, sizeof dp);
for(ll i = 0;i < n-1;i++){
g[U[i]+1].push_back({V[i]+1, W[i]});
g[V[i]+1].push_back({U[i]+1, W[i]});
}
vector <ll> ans;
for(ll k = 0;k < n;k++){
solve(1, 1, k, 0);
ans.push_back(dp[1][k][0]);
}
return ans;
}
