#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
int N;
vector<pii> adj[MAXN+10];
int par[MAXN+10], val[MAXN+10], sz[MAXN+10];
ll ans[MAXN+10];
int K;
vector<ll> dp1[MAXN+10], dp2[MAXN+10];
void dfs(int now, int bef)
{
sz[now]=1;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs(nxt.first, now);
par[nxt.first]=now;
val[nxt.first]=nxt.second;
sz[now]+=sz[nxt.first];
}
}
/*
void dfs2(int now, int bef)
{
vector<ll> V;
ll p=0;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs2(nxt.first, now);
V.push_back(dp1[nxt.first]-dp2[nxt.first]);
p+=dp2[nxt.first];
}
sort(V.begin(), V.end());
for(int i=0; i<K-1 && i<V.size(); i++)
{
if(V[i]<0) p+=V[i];
}
dp1[now]=p;
if(K-1<V.size() && V[K-1]<0) p+=V[K-1];
dp2[now]=p+val[now];
}
*/
void dfs2(int now, int bef)
{
vector<int> chd;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs2(nxt.first, now);
chd.push_back(nxt.first);
}
sort(chd.begin(), chd.end(), [&](const int &p, const int &q)
{
return sz[p]>sz[q];
});
dp1[now]=dp2[now]=vector<ll>(sz[now]);
for(int i=0; i<sz[now]; i++)
{
ll p=0;
vector<ll> V;
for(auto it : chd)
{
if(i>=dp2[it].size())
{
p+=val[it];
V.push_back(-val[it]);
continue;
}
p+=dp2[it][i];
V.push_back(dp1[it][i]-dp2[it][i]);
}
sort(V.begin(), V.end());
for(int j=0; j<i-1 && j<V.size(); j++)
{
if(V[j]<0) p+=V[j];
}
dp1[now][i]=p;
if(i-1<V.size() && V[i-1]<0) p+=V[i-1];
dp2[now][i]=p+val[now];
}
}
vector<ll> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W)
{
N=_N;
for(int i=0; i<N-1; i++)
{
int u=_U[i], v=_V[i], w=_W[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(1, 1);
dfs2(1, 1);
for(int i=0; i<N; i++) ans[i]=dp2[1][i];
return vector<ll>(ans, ans+N);
}
