#include "roads.h"
#include <bits/stdc++.h>
using namespace std;

const int NN=1e5+5;
int n;
long long dp[NN][2];
vector<pair<int,int>> g[NN];

void dfs(int x, int p, int k) {
    vector<long long> v; long long val=0;
    for (auto AA:g[x]) {
        int y=AA.first,w=AA.second;
        if (y==p) continue;
        dfs(y,x,k);
        val+=dp[y][0]; v.push_back(w-max(0ll,dp[y][0]-dp[y][1]));
    }
    int sz=v.size();
    sort(v.begin(),v.end());
    dp[x][0]=val; dp[x][1]=val;
    if (x==0) {
        for (int i=sz-1; i>=k; i--) dp[x][0]+=v[i];
        for (int i=sz-1; i>=k+1; i--) dp[x][1]+=v[i];
    }
    else {
        if (k==0) dp[x][0]=1e15;
        else for (int i=sz-1; i>=k-1; i--) dp[x][0]+=v[i];
        for (int i=sz-1; i>=k; i--) dp[x][1]+=v[i];
    }
}

long long solve(int k) {
    dfs(0,0,k);
    // for (int i=0; i<n; i++) cout<<i<<" "<<dp[i][1]<<" "<<dp[i][0]<<endl;
    return dp[0][0];

}

vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    vector<long long> ans(N,0); n=N;
    for (int i=0; i<N; i++) {
        g[U[i]].emplace_back(V[i],W[i]);
        g[V[i]].emplace_back(U[i],W[i]);
    }

    for (int k=0; k<n; k++) ans[k]=solve(k);
    return ans;
}