#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
vector<vector<pair<int,int>>> v(100005);
long long dp[100005][2];
void run(int x,int p,int k)
{
int y,w;
dp[x][0]=0;
dp[x][1]=0;
for(int i=0;i<v[x].size();i++)
{
y=v[x][i].s;
if(y==p)
continue;
run(y,x,k);
}
vector<long long> sorta;
for(int i=0;i<v[x].size();i++)
{
w=v[x][i].f;
y=v[x][i].s;
if(y==p)
continue;
dp[x][0]+=dp[y][0];
dp[x][1]+=dp[y][0];
sorta.push_back(dp[y][1]+w-dp[y][0]);
}
sort(sorta.begin(),sorta.end());
int cut=sorta.size()-k;
for(int i=0;i<sorta.size();i++)
{
if(i<cut)
dp[x][1]+=sorta[i];
else if(sorta[i]<0)
dp[x][1]+=sorta[i];
}
for(int i=0;i<sorta.size();i++)
{
if(i<cut+1)
dp[x][0]+=sorta[i];
else if(sorta[i]<0)
dp[x][0]+=sorta[i];
}
return;
}
vector<long long> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W)
{
vector<long long> ans;
int x,y,w,p;
for(int i=0;i<N-1;i++)
{
x=U[i];
y=V[i];
w=W[i];
x++;
y++;
v[x].push_back({w,y});
v[y].push_back({w,x});
}
int st;
for(int i=1;i<=N;i++)
{
if(v[i].size()==1)
{
st=i;
break;
}
}
for(int i=0;i<N;i++)
{
run(st,0,i);
ans.push_back(min(dp[st][0],dp[st][1]));
}
return ans;
}
