#include "roads.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ar array
const int N = 2e3 + 5;
vector<ar<int, 2>> edges[N];
ll dp[N][N][2];
void dfs(int u, int p = -1){
for(auto x : edges[u]){
if(x[0] == p) continue;
dfs(x[0], u);
}
for(int t=0;t<2;t++){
for(int j=0;j<N;j++){
vector<ll> tt;
for(auto x : edges[u]){
if(x[0] == p) continue;
dp[u][j][t] += x[1] + dp[x[0]][j][0];
if(j) tt.push_back(dp[x[0]][j][1] - x[1] - dp[x[0]][j][0]);
}
sort(tt.begin(), tt.end());
for(int l=0;l<min((int)tt.size(), j - t);l++){
dp[u][j][t] += tt[l];
}
}
}
//~ for(int t=0;t<2;t++){
//~ for(int k=0;k<5;k++){
//~ cout<<dp[u][k][t]<<" ";
//~ } cout<<"\n";
//~ }
}
vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
for(int i=0;i<n-1;i++){
edges[v[i]].push_back({u[i], w[i]});
edges[u[i]].push_back({v[i], w[i]});
}
dfs(0);
vector<ll> res;
for(int k=0;k<n-1;k++){
res.push_back(dp[0][k][0]);
} return res;
}
/*
5
0 1 1
0 2 4
0 3 3
2 4 2
*/
