#include <bits/stdc++.h>
#include "roads.h"
// #include "grader.cpp"
using namespace std;
using ll = long long;
#define sz(v) (int)(v).size()
vector<vector<ll>> dp;
vector<vector<pair<int, int>>> E;
void dfs(int x, int k, int p = -1) {
for (auto [i, w] : E[x]) {
if (i != p) {
dp[i][0] = w;
dfs(i, k, x);
}
}
vector<ll> v;
for (auto [i, w] : E[x]) {
if (i == p) continue;
dp[x][0] += dp[i][1];
dp[x][1] += dp[i][1];
v.push_back(dp[i][0] - dp[i][1]);
}
sort(v.begin(), v.end());
for (int i = 0; i < sz(v); i++) {
dp[x][0] += (i < sz(v) - k || v[i] < 0 ? v[i] : 0);
dp[x][1] += (i <= sz(v) - k || v[i] < 0 ? v[i] : 0);
}
}
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) {
E.assign(n, {});
for (int i = 0; i < n - 1; i++) {
E[U[i]].push_back({V[i], W[i]});
E[V[i]].push_back({U[i], W[i]});
}
vector<ll> v(n);
for (int i = 0; i < n; i++) {
dp.assign(n, vector<ll>(2));
dfs(0, i);
v[i] = dp[0][0];
}
return v;
}
