#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define int2 int32_t
#define inf 5e18
#define nl '\n'
const int N = 2000;
vector<pair<int,int>> g[N];
int dp[N][2];
void dfs(int v, int p, int t, int k){
vector<int> vec;
int sum = 0;
for(auto [ch, w] : g[v]){
if(ch == p) continue;
dfs(ch, v, w, k);
if(dp[ch][1] != -1) vec.push_back(dp[ch][1] - dp[ch][0]);
sum += dp[ch][0];
}
sort(vec.rbegin(), vec.rend());
for(int i=0; i < min(k-1, (int)vec.size()); i++) sum += vec[i];
dp[v][1] = sum + t;
if(k == 0 and g[v].size() == 0) dp[v][1] = -1;
if(k-1 < vec.size()) sum += vec[k-1];
dp[v][0] = sum;
}
vector<int> minimum_closure_costs(int2 n, vector<int2> a, vector<int2> b, vector<int2> w){
int tot = 0;
for(int i=0; i<n-1; i++){
g[a[i]].push_back({b[i], w[i]});
g[b[i]].push_back({a[i], w[i]});
tot += w[i];
}
vector<int> ans(n);
for(int i=0; i<n; i++){
dfs(0, 0, 0, i);
ans[i] = tot - dp[0][0];
}
return ans;
}
