#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], dp1[N];
vector <pair <int, ll>> 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(dp1[i] + w - dp[i]);
dp[x] += dp[i];
}
dp1[x] = dp[x];
sort(v1.rbegin(), v1.rend());
for(int i = 0; i < min(SZ(v1), k); i++) {
dp[x] += max(v1[i], 0LL);
if(i < k - 1) dp1[x] += 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++) {
for(int j = 0; j < n; j++) {
dp[j] = dp1[j] = 0;
}
f(0, -1, k);
ans[k] = (s - dp[0]);
}
return ans;
}
