#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W){
vector<pii> g[n + 1];
ll tot = 0;
for (int i = 0; i < n - 1; i++){
int u = U[i] + 1, v = V[i] + 1, w = W[i];
g[u].pb({v, w});
g[v].pb({u, w});
tot += w;
}
vector<vector<pll>> f(n, vector<pll>(n + 1));
for (int k = 1; k < n; k++){
function<void(int, int)> dfs = [&](int v, int pr){
for (auto [i, w]: g[v]){
if (i == pr) continue;
dfs(i, v);
}
vector<ll> all;
ll sum = 0;
for (auto [i, w]: g[v]){
if (i == pr) continue;
sum += f[k][i].ss;
all.pb(f[k][i].ff + w - f[k][i].ss);
}
sort(all.begin(), all.end(), greater<ll>());
f[k][v].ff = sum;
for (int i = 0; i < min((int) all.size(), k - 1); i++){
if (all[i] <= 0) break;
f[k][v].ff += all[i];
}
f[k][v].ss = sum;
for (int i = 0; i < min((int) all.size(), k); i++){
if (all[i] <= 0) break;
f[k][v].ss += all[i];
}
};
dfs(1, 0);
}
int cnt = 0;
for (int v = 1; v <= n; v++){
for (int k = 1; k < n; k++){
if (f[k - 1][v].ff != f[k][v].ff){
cnt++;
}
if (f[k - 1][v].ss != f[k][v].ss){
cnt++;
}
}
}
assert(cnt <= (6 * n));
vector<ll> out;
for (int i = 0; i < n; i++){
out.pb(tot - f[i][1].ss);
}
return out;
}
