#include "roads.h"
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vi vector<int>
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
const int mxn = 1e5 + 5;
vector<pair<int,int>>adj[mxn]; int n, k; int dp[mxn][2];
void dfs(int node, int from){
int sum = 0, deg = 0; vi dif;
for(auto [u,w] : adj[node])if(u!=from)dfs(u,node), deg++, sum+=max(dp[u][0],dp[u][1]), dif.pb(dp[u][0]+w-max(dp[u][0],dp[u][1])); sort(dif.rbegin(),dif.rend());
if(deg >= k){
dp[node][1]=sum; f0r(i,k)dp[node][1]+=dif[i];
}
dp[node][0]=sum; f0r(i,min(k-1,(int)dif.size())){
if(dif[i]<0)break; dp[node][0]+=dif[i];
}
}
std::vector<long long> minimum_closure_costs(signed N, std::vector<signed> U,
std::vector<signed> V,
std::vector<signed> W) {
n=N; vi ans; int S = 0; f0r(i,n-1)adj[U[i]].eb(V[i],W[i]),adj[V[i]].eb(U[i],W[i]),S+=W[i]; f0r(K,n){
k=K; f0r(i,n)f0r(j,2)dp[i][j]=0; dfs(0,-1); ans.pb(S-max(dp[0][0],dp[0][1]));
} return ans;
}
