long long dir(long long x){return x<0?-1:x>0?1:0;}
int max(int i,int j){return i>j?i:j;}
#define assert(x) if(!(x))__builtin_trap()
#include "roads.h"
#include<stdlib.h>
#include <vector>
#define NN 2000
#define MM (2*NN)
int head[NN], nxt[MM], vv[MM], ww[MM];
void link(int u,int v,int w)
{
static int i=1;
nxt[i]=head[u];
vv[i]=v;
ww[i]=w;
head[u]=i++;
}
long long dp_loose[NN], dp_tight[NN];
typedef struct { long long a, b; } ab;
int abdec(ab a, ab b) { if(a.a^b.a)return -dir(a.a-b.a);return -dir(a.b-b.b);}
int ij(const void*ii,const void*jj){return dir(*(const long long*)ii-*(const long long*)jj);}
void dfs(int u,int p,int k)
{
for(int j=head[u];j;j=nxt[j])if(vv[j]-p)
dfs(vv[j], u, k);
static long long aa[NN], sum;
int ao, i;
sum = 0;
ao = 0;
for(int j=head[u];j;j=nxt[j])if(vv[j]-p)
{
int v=vv[j],w=ww[j];
aa[ao++] = -(w + dp_tight[v] - dp_loose[v]);
sum += w + dp_tight[v];
}
/* for tight : can have at most k alive children
* for loose : can have at most k-1 alive children
*
*/
qsort(aa, ao, sizeof*aa, ij);
dp_tight[u] = sum;
for (i = 0; i < ao && i < k && aa[i] <= 0; ++i)
dp_tight[u] += aa[i];
dp_loose[u] = sum;
for (i = 0; i < ao && i < k - 1 && aa[i] <= 0; ++i)
dp_loose[u] += aa[i];
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
if(N>2000)__builtin_unreachable();
for(int i=0;i<N-1;++i)link(U[i],V[i],W[i]),link(V[i],U[i],W[i]);
std::vector<long long> ans(N);
for(int k=0;k<N;++k)
dfs(0, 0, k), ans[k] = dp_tight[0];
return ans;
}
