#include "roads.h"
#define _GLIBCXX_DEBUG 1
#pragma GCC optimize "O3,unroll-loops,trapv"
#include <bits/stdc++.h>
#define REP(i,o,n) for(int i=o;i<n;i++)
#define FORI(v) for(auto i:v)
#define FORJ(v) for(auto j:v)
#define FORK(v) for(auto i:v)
#define fi first
#define se second
#define pb push_back
using namespace std;
using pii = pair<int,int>;
long long memo[3000][3];
int k;
vector<pii> adj[3000];
long long dp(int node, int parent, bool shadow){
if(shadow && k==0)return 1e18;
if(adj[node].size()==1 && (parent != -1))return 0;
long long &ans=memo[node][shadow];
if(ans!=-1)return ans;
ans = 0;
vector<int> addgains;
FORI(adj[node]){
if(i.fi==parent)continue;
ans += dp(i.fi, node, false) + i.se;
addgains.pb(dp(i.fi,node,true) - (dp(i.fi, node, false) + i.se));
}
sort(addgains.begin(), addgains.end());
int limit = k;
if(shadow)limit--;
limit=min<int>(addgains.size(), limit);
REP(i,0,limit){
if(addgains[i]>0)break;
ans += addgains[i];
}
return ans;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
REP(i,0,N-1){
adj[U[i]].pb({V[i], W[i]});
adj[V[i]].pb({U[i], W[i]});
}
vector<long long>ans;
REP(i,0,N){
memset(memo,-1,sizeof memo);
k = i;
ans.pb(dp(0,-1,0));
ans.pb(dp(0,-1,true));
ans.pop_back();
// cerr<<"=== k="<<i<<" ===\n";
// REP(j,0,N)cerr<<j<<": "<<memo[j][0]<<" / "<<memo[j][1]<<'\n';
// cerr<<endl<<endl;
}
return ans;
}
