#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e12;
int n;
vt<vt<pl>> adj;
vt<ll> ans;
pl dfs(int u, int k, int par = -1) { // {take parent edge, dont take parent edge}
vt<ll> diff;
ll take_cost = 0;
for (auto [v, w] : adj[u]) {
if (v == par) continue;
auto [take, dont_take] = dfs(v, k, u);
take_cost += dont_take;
diff.pb(take - dont_take + w);
}
ll dont_take_cost = take_cost;
ll req = adj[u].size() - k;
sort(all(diff));
F0R (i, req - 1) {
take_cost += diff[i];
dont_take_cost += diff[i];
}
if (req > 0) {
if (diff.size() <= req - 1) {
dont_take_cost += INF;
} else {
dont_take_cost += diff[req - 1];
}
}
return {take_cost, dont_take_cost};
}
vt<ll> minimum_closure_costs(int _n, vt<int> u, vt<int> v, vt<int> w) {
n = _n;
adj.resize(n);
F0R (i, n - 1) {
adj[u[i]].pb({v[i], w[i]});
adj[v[i]].pb({u[i], w[i]});
}
ans.resize(n);
ROF (k, 0, n) {
ans[k] = dfs(0, k).s;
}
return ans;
}
