#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef pair<int,ll> pil;
typedef vector<pil> vpil;
typedef vector<vpil> vvpil;
struct tree{
int N;
vvpil C;
vi F;
vl FW, dp1, dp2;
void dfs(int v = 0, int prev = -1){
if(prev != -1){
for(int i = 0;i < C[v].size();i++){
if(C[v][i].first == prev){
C[v].erase(C[v].begin() + i);
break;
}
}
}
for(auto [u,w] : C[v]){
F[u] = v;
FW[u] = w;
dfs(u,v);
}
}
tree(int N, vi U, vi V, vi W) : N(N) {
C.assign(N,{});
for(int i = 0;i < N-1;i++) C[U[i]].emplace_back(V[i],W[i]), C[V[i]].emplace_back(U[i],W[i]);
F.assign(N,0);
FW.assign(N,0);
dp1 = dp2 = FW;
dfs();
}
void test(int k, int v = 0) {
ll base = 0;
vl imp;
for(auto [u,w] : C[v]){
test(k,u);
base += dp1[u];
imp.push_back(dp2[u] - dp1[u]);
}
sort(imp.begin(),imp.end());
dp1[v] = dp2[v] = base;
for(int i = 0;i < min(k,(int)imp.size()) && imp[i] < 0;i++) dp1[v] += imp[i];
dp1[v] += FW[v];
for(int i = 0;i < min(k-1,(int)imp.size()) && imp[i] < 0;i++) dp2[v] += imp[i];
dp2[v] = min(dp2[v],dp1[v]);
}
};
vl minimum_closure_costs(int N, vi U, vi V, vi W) {
tree T(N,U,V,W);
vl Ans(N,0);
for(int k = 0;k < N;k++){
T.test(k);
Ans[k] = T.dp2[0];
}
return Ans;
}
