#include "roads.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<pair<long long, long long>> g[400001];
vector<long long> v;
long long n, i, j;
long long dp[400001][2];
void dfs(long long x, long long pr, long long k, long long c) {
for (auto y : g[x]) if (y.first != pr) dfs(y.first, x, k, y.second);
vector<long long> vv;
for (auto y : g[x]) {
if (y.first == pr) continue;
dp[x][0] += dp[y.first][0];
}
dp[x][1] = dp[x][0];
for (auto y : g[x]) {
if (y.first == pr) continue;
vv.push_back({-dp[y.first][0] + dp[y.first][1] + y.second});
}
sort(vv.begin(), vv.end());
//long long w = vv.size() * 52;
long long w = (long long)vv.size() - k;
//for (long long i = 0; i < min((long long)vv.size(), w + 1); i++) {
for (long long i = 0; i < min((long long)vv.size(), w + 1); i++) {
dp[x][0] += vv[i];
}
for (long long i = 0; i < w; i++) {
dp[x][1] += vv[i];
}
//cout << x << " " << dp[x][0] << " " << dp[x][1] << "\n";
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
for (long long i = 0; i < N - 1; i++) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
for (long long i = 0; i < N; i++) {
for (long long j = 0; j <= N; j++) dp[j][0] = dp[j][1] = 0;
dfs(0, 0, i, 0);
v.push_back(dp[0][1]);
}
return v;
}
/*
*
5
0 1 1
0 2 4
0 3 3
2 4 2
* */
