#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge {
int to, w;
};
ll solve(const vector<vector<Edge>> &g, int k) {
int n = g.size();
vector<ll> dp0(n), dp1(n);
auto dfs = [&](auto &&self, int u, int p) -> void {
ll base = 0;
vector<ll> delta;
for (auto [v, w] : g[u]) {
if (v == p)
continue;
self(self, v, u);
base += dp0[v];
delta.push_back(dp1[v] + w - dp0[v]);
}
sort(delta.begin(), delta.end());
auto get = [&](int can_keep) -> ll {
int m = delta.size();
int keep = max(0, can_keep);
keep = min(keep, m);
int need_close = m - keep;
ll res = base;
for (int i = 0; i < need_close; ++i)
res += delta[i];
return res;
};
dp1[u] = get(k);
dp0[u] = get(k - 1);
};
dfs(dfs, 0, -1);
return dp1[0];
}
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V,
vector<int> W) {
vector<vector<Edge>> g(N);
for (int i = 0; i < N - 1; ++i) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
vector<ll> ans(N);
for (int k = 0; k < N; ++k)
ans[k] = solve(g, k);
return ans;
}
