#include "roads.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MxN = 25e4 + 5;
ll dp[MxN][2];
vector<pii> v[MxN];
void dfs (int cur, int par, int k) {
vector<ll> c;
for (auto &[x, y]: v[cur]) {
if (par == x) continue;
dfs(x, cur, k);
dp[cur][0] += dp[x][1]; dp[cur][1] += dp[x][1];
c.emplace_back(dp[x][0] + y - dp[x][1]);
}
sort(c.rbegin(), c.rend());
for (int i = 0; i < min(k - 1, (int) c.size()); i++) dp[cur][0] = max(dp[cur][0], dp[cur][0] + c[i]);
for (int i = 0; i < min(k, (int) c.size()); i++) dp[cur][1] = max(dp[cur][1], dp[cur][1] + c[i]);
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
int n = N, m = U.size();
ll res = 0;
for (int i = 0; i < m; i++) v[U[i]].emplace_back(V[i], W[i]), v[V[i]].emplace_back(U[i], W[i]), res += W[i];
vector<ll> ans;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) dp[j][0] = dp[j][1] = 0;
dfs(0, -1, i);
ans.emplace_back(res - dp[0][1]);
}
return ans;
}
