#define wiwihorz
#include "roads.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define INF 1e15
#define eps (1e-9)
#define MOD 1000000007
using namespace std;
#define ll long long int
#define pii pair<int, int>
#define radom mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
struct ac {
ll sum, x, cnt;
priority_queue<ll> pq;
stack<ll> st;
void init_() {
sum = 0, x = 0, cnt = 0;
while(st.size()) st.pop();
while(pq.size()) pq.pop();
}
void maintain() {
while(pq.size() > x) {
ll cur = pq.top(); pq.pop();
sum -= cur;
}
}
void set(ll _x) { x = max(0ll, _x); }
void add(ll v) { pq.push(v), sum += v; }
void pop() {
if(!pq.size()) return;
ll cur = pq.top(); pq.pop();
st.push(cur), cnt ++;
sum -= cur;
}
void redo() {
assert(cnt), cnt --;
ll cur = st.top(); st.pop();
sum += cur, pq.push(cur);
}
ll get_val(bool yes) {
maintain();
return sum - yes * (pq.size() ? pq.top() : 0);
}
};
namespace solver {
ll n, ii, temp;
vector<ll> pri, dp0, dp1, deg, vis, es, cost;
vector<vector<ll>> mp;
vector<ac> s;
void init_(ll _n) {
n = _n, ii = 0;
pri.assign(n, 0);
dp0.assign(n + 1, 0);
dp1.assign(n + 1, 0);
deg.assign(n + 1, 0);
vis.assign(n + 1, 0);
s.assign(n + 1, ac());
mp.assign(n + 1, vector<ll>());
rep(i, 1, n) {
pri[i - 1] = i;
s[i].init_();
}
}
void add_edge(ll a, ll b, ll c) {
mp[a].push_back(es.size());
mp[b].push_back(es.size());
es.push_back(a ^ b);
cost.push_back(c);
deg[a] ++, deg[b] ++;
}
void dfs(ll x, ll par, ll k) {
vis[x] = k + 1;
dp1[x] = INF, dp0[x] = INF;
vector<ll> v;
ll cnt = 0, sum = 0;
for(auto i : mp[x]) if(i != par) {
ll to = es[i] ^ x;
if(deg[to] <= k) break;
dfs(to, i, k);
v.push_back(dp1[to] + cost[i] - dp0[to]);
sum += dp0[to], cnt ++;
}
sort(all(v));
s[x].set(deg[x] - k);
s[x].maintain();
ll to = s[x].x - s[x].pq.size();
if(v.size() >= to) {
ll cur = 0;
rep(i, 0, to - 1) cur += v[i];
dp0[x] = min(dp0[x], sum + cur + s[x].get_val(0));
rep(j, to, cnt - 1) {
cur += v[j];
s[x].pop(), s[x].set(s[x].x - 1);
dp0[x] = min(dp0[x], sum + cur + s[x].get_val(0));
}
s[x].set(deg[x] - k);
while(s[x].cnt) s[x].redo();
}
s[x].set(deg[x] - k - 1);
s[x].maintain();
to = s[x].x - s[x].pq.size();
if(v.size() >= to) {
ll cur = 0;
rep(i, 0, to - 1) cur += v[i];
dp1[x] = min(dp1[x], sum + cur + s[x].get_val(0));
rep(j, to, cnt - 1) {
cur += v[j];
s[x].pop(), s[x].set(s[x].x - 1);
dp1[x] = min(dp1[x], sum + cur + s[x].get_val(0));
}
s[x].set(deg[x] - k - 1);
while(s[x].cnt) s[x].redo();
}
}
vector<ll> solve() {
sort(all(pri), [](ll a, ll b) {return deg[a] < deg[b];});
rep(i, 1, n) temp = i, sort(all(mp[i]),
[](ll a, ll b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
vector<ll> aa(n, 0);
rep(i, 0, n - 1) {
while(ii < n && deg[pri[ii]] <= i) {
dp0[pri[ii]] = 0;
dp1[pri[ii]] = 0;
for(auto j : mp[pri[ii]]) {
ll to = es[j] ^ pri[ii];
if(deg[to] > i) s[to].add(cost[j]);
}
ii++;
}
ll ans = 0;
rep(j, ii, n - 1) if(vis[pri[j]] != i + 1){
dfs(pri[j], -1, i);
ans += dp0[pri[j]];
}
aa[i] = ans;
}
return aa;
}
};
using namespace solver;
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
init_(N);
rep(i, 0, N - 2) add_edge(U[i] + 1, V[i] + 1, W[i]);
return solve();
}
