#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 7;
const long long INF = (long long)1e18 + 7;
const long long oo = (long long)1e15 + 7;
const int inf = (int)1e9 + 7;
int n, k;
long long dp[N][2];
vector<pair<int, int> > g[N];
struct Data {
long long x, y;
};
void dfs(int v, int pr, int last) {
for(auto [to, w] : g[v]) {
if(to == pr) {
continue;
}
dfs(to, v, w);
}
long long tot = 0;
vector<long long> cur;
for(auto [to, w] : g[v]) {
if(to == pr) {
continue;
}
tot += dp[to][1];
cur.push_back(dp[to][0]-dp[to][1]);
}
sort(cur.begin(), cur.end());
dp[v][1] = tot+last;
if(k+(v == pr)) {
dp[v][0] = tot;
for(int i = 0; i < min((int)cur.size(), k); ++i) {
if(cur[i] > oo) {
break;
}
tot += cur[i];
if(i < k+(v == pr)-1) {
dp[v][0] = min(dp[v][0], tot);
}
dp[v][1] = min(dp[v][1], tot+last);
}
} else {
dp[v][0] = INF;
}
}
vector<long long> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W) {
n = _N;
for(int i = 0; i < n-1; ++i) {
int u = _U[i];
int v = _V[i];
int w = _W[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<long long> ans;
for(int i = 0; i < n; ++i) {
k = i;
dfs(0, 0, inf);
ans.push_back(dp[0][0]);
}
return ans;
}
