#include "bits/stdc++.h"
#include "roads.h"
// #include "grader.cpp"
using namespace std;
#define ll long long
#define SZ(s) (int)s.size()
const int N = 2e3 + 5;
ll n, dp[N][N];
vector <pair <int, int>> v[N];
void f(int x, int y, int k) {
vector <ll> v1;
for(auto [i, w] : v[x]) {
if(i == y) continue;
f(i, x, k);
v1.push_back(((!k ? 0 : dp[i][k-1]) + w - dp[i][k]));
dp[x][k] += dp[i][k];
}
sort(v1.rbegin(), v1.rend());
for(int i = 0; i < min(SZ(v1), k); i++) {
dp[x][k] += max(v1[i], 0LL);
}
return;
}
vector<ll> minimum_closure_costs(int NN, vector<int> u1, vector<int> u2, vector<int> w) {
n = NN;
vector <ll> ans(n, 0);
ll s = 0;
for(int i = 0; i < n-1; i++) {
v[u1[i]].push_back({u2[i], w[i]});
v[u2[i]].push_back({u1[i], w[i]});
s += w[i];
}
for(int k = 0; k < n; k++) {
f(0, -1, k);
ans[k] = (s - dp[0][k]);
}
return ans;
}
