#include "roads.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, k;
vector<vector<pair<int, int>>> tree;
vector<ll> dp[2];
vector<ll> pe;
void pre_dfs(int nd, int ss){
for(auto [x, w]: tree[nd]) if(x != ss) pre_dfs(x, nd), pe[x] = w;
}
void dfs(int nd, int ss){
ll sum = 0;
vector<int> o;
for(auto [x, w]: tree[nd]) if(x != ss) dfs(x, nd), sum+=dp[1][x], o.pb(x);
dp[0][nd] = sum, dp[1][nd] = sum;
sort(o.begin(), o.end(), [&](int a, int b){
return -dp[1][a]+dp[0][a]+pe[a] > -dp[1][b]+dp[0][b]+pe[b];
});
for(int i = k; i < o.size(); i++) dp[0][nd]+=-dp[1][o[i]]+dp[0][o[i]]+pe[o[i]];
for(int i = k-1; i < o.size(); i++) dp[1][nd]+=-dp[1][o[i]]+dp[0][o[i]]+pe[o[i]];
}
vector<ll> minimum_closure_costs(int _n, vector<int> U, vector<int> V, vector<int> W){
swap(n, _n);
tree.resize(n);
pe.resize(n);
for(int i = 0; i < n-1; i++){
tree[U[i]].pb({V[i], W[i]});
tree[V[i]].pb({U[i], W[i]});
}
pre_dfs(0, -1);
vector<ll> ans(n, 0);
for(k = 0; k < n; k++){
if(k == 0){
for(int x: W) ans[k]+=x;
continue;
}
fill(dp, dp+2, vector<ll>(n, 0));
dfs(0, -1);
ans[k] = dp[0][0];
}
return ans;
}
