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

#ifdef DEBUG
#include "debug.cpp"
#else
#define dbg(...)
#define dbgarr(...)
#endif




// given nodes, construct a tree such that the tree has maximum weight and each node is connected
// to at most k nodes

// greedy aka removing road with most weight doesnt work
struct Edge{
    int u, v, w;
} G;

bool visited[2005];
int N;

bool cmp(const Edge &x, const Edge &y){
    return x.w > y.w;
}

ll visit(int u, int k, vector<Edge>&G){
    if(k == 0)return 0;
    int deg[N], mx=G[u].w;
    memset(deg,0,sizeof(deg));
    deg[G[u].u]++;
    deg[G[u].v]++;

    for(int i=0; i<N-1; i++){
        if(i == u)continue;
        if(deg[G[i].u]+1 <= k && deg[G[i].v]+1<=k){
            // can add
            deg[G[i].u]++;
            deg[G[i].v]++;
            visited[i] = 1;
            mx += G[i].w;
        }
    }

    return mx;
}


std::vector<long long> minimum_closure_costs(int _N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    N = _N;
    vector<Edge> G;
    ll sum=0;
    vector<ll> ans(N,0);
    for(int i=0; i<N-1; i++){
        sum += W[i];
        G.push_back({U[i], V[i], W[i]});
    }
    sort(G.begin(), G.end(), cmp);

    for(int k=0; k<N; k++){
        memset(visited,0,sizeof(visited));
        ll curans = 0;
        // choose max k edge
        for(int i=0; i<N-1; i++){
            if(!visited[i]){
                ll cur = visit(i, k, G);
                curans = max(curans, cur);
            }
        }
        ans[k] = sum - curans;
    }


    return ans;
}