#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100'000 + 10;
const long long MAX = 1'000'000'000'000'000;
int n;
vector<pair<int, int>> ad[MAXN];
long long parW[MAXN];
int k;
long long f[MAXN][2];
void dfs(int u, int p = -1) {
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
parW[v] = w;
dfs(v, u);
}
long long sum = 0;
vector<long long> best;
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
sum += min(f[v][0], f[v][1]);
best.push_back(f[v][1] - min(f[v][0], f[v][1]));
}
sort(best.begin(), best.end());
int cnt = ad[u].size() - k;
if (cnt <= (int)best.size()) {
f[u][0] = sum + accumulate(best.begin(), best.begin() + max(0, cnt), 0ll);
f[u][1] = sum + accumulate(best.begin(), best.begin() + max(0, cnt - 1), 0ll) + parW[u];
} else {
f[u][0] = MAX;
f[u][1] = sum + accumulate(best.begin(), best.end(), 0ll) + parW[u];
}
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
n = N;
for (int i = 0; i < n - 1; ++i) {
int u = U[i], v = V[i], w = W[i];
ad[u].push_back({v, w});
ad[v].push_back({u, w});
}
parW[0] = MAX;
vector<long long> ret;
for (k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) f[i][0] = f[i][1] = MAX;
dfs(0);
ret.push_back(f[0][0]);
}
return ret;
}
