#include<bits/stdc++.h>
#include "roads.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) int32_t(x.size())
#define int long long
const int maxn = 2e3+10;
const int inf = 1e18+10;
int n, dp[maxn][2];
vector<int> g[maxn];
vector<pair<int,int>> gesp[maxn];
void dfs(int u, int qtd, int ant) {
// mark[u] = qtd+1;
int ans = 0;
vector<int> use;
for(auto V : gesp[u]) if(V.fr != ant) {
int v = V.fr;
int w = V.sc;
dfs(v,qtd,u);
ans+= min(dp[v][0],dp[v][1]+w);
use.pb(-min(dp[v][0],dp[v][1]+w)+dp[v][1]+w);
}
sort(all(use));
//se nao tem a aresta com o pai -> sz(g[u])-1-qtd = t
dp[u][0] = dp[u][1] = inf;
if(sz(g[u])-qtd-1 <= 0) dp[u][1] = ans;
if(sz(g[u])-qtd <= 0) dp[u][0] = ans;
for(int i = 1; i <= sz(g[u])-qtd; i++) {
ans+= use[i-1];
if(i == sz(g[u])-qtd-1) dp[u][1] = ans;
if(i == sz(g[u])-qtd) dp[u][0] = ans;
}
}
std::vector<int> minimum_closure_costs(int32_t N, std::vector<int32_t> U,std::vector<int32_t> V,std::vector<int32_t> W) {
n = N;
vector<int> ans;
int sumw = 0;
for(int i = 0; i < n-1; i++) {
int u = U[i];
int v = V[i];
int w = W[i];
sumw+= w;
g[u].pb(i);
g[v].pb(i);
gesp[u].pb(mp(v,w));
gesp[v].pb(mp(u,w));
}
ans.pb(sumw);
for(int k = 1; k <= n-1; k++) {
dfs(0,k,-1);
ans.pb(dp[0][0]);
}
return ans;
// for(int i = 0; i < n; i++) {
// gr[g[i].size()].pb(i);
// }
// vector<int> esp;
// vector<int> ans;
// for(int i = 0; i < n; i++) {
// int ans1 = 0;
// for(auto u : gr[i]) {
// esp.pb(u);
// atv[u] = 1;
// for(auto id : g[u]) {
// int v = u^U[id]^V[id];
// int w = W[id];
// if(atv[v]) {
// gesp[u].pb(mp(v,w));
// gesp[v].pb(mp(u,w));
// }
// }
// }
// for(auto v : esp) {
// if(mark[v] != i+1) dfs(v,i,-1);
// }
// }
return std::vector<long long>(N, 0);
}
