#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 1e5 + 5;
int n;
vector<int>u, v, w, g[lim];
namespace sub1{
vector<ll>solve(){
sort(w.begin(), w.end(), greater<int>());
vector<ll>ans(n);
ans[n - 1] = 0;
for(int i = n - 2; i > -1; i--){
ans[i] = ans[i + 1] + w[i];
}
return ans;
}
}
namespace sub2{
bool check_subtask(){
for(int i = 0; i + 1 < n; i++){
if(u[i] != i || v[i] != i + 1){
return false;
}
}
return true;
}
vector<ll>solve(){
vector<ll>dp(2, 0), ndp(2);
for(int i = 0; i + 1 < n; i++, swap(dp, ndp)){
ndp[0] = dp[1];
ndp[1] = min(dp[0], dp[1]) + w[i];
}
vector<ll>ans(n, 0);
ans[0] = accumulate(w.begin(), w.end(), 0LL);
ans[1] = min(dp[0], dp[1]);
return ans;
}
}
namespace sub34{
vector<ll>solve(){
vector<ll>ans(n);
ans[0] = accumulate(w.begin(), w.end(), 0LL);
for(int k = 1; k < n; k++){
function<pair<ll, ll>(int, int)>dfs;
dfs = [&] (int s, int p){
vector<pair<ll, ll>>child;
for(int& i : g[s]){
int d = u[i] ^ v[i] ^ s;
if(d != p){
pair<ll, ll>dv = dfs(d, s);
child.push_back(make_pair(dv.first, min(dv.first, dv.second) + w[i]));
}
}
pair<ll, ll>ans = make_pair(0, 0);
ll sum = 0;
int need = int(g[s].size()) - k;
vector<ll>dif;
for(auto& [u, v] : child){
if(v <= u){
need--;
sum += v;
}
else{
sum += u;
dif.push_back(v - u);
}
}
sort(dif.begin(), dif.end());
for(int i = 0; i < need; i++){
sum += dif[i];
}
ans.first = ans.second = sum;
if(need > 0){
ans.second -= dif[need - 1];
}
return ans;
};
ans[k] = dfs(0, -1).first;
}
return ans;
}
}
namespace sub5{
vector<ll>solve(){
vector<ll>ans(n, 0);
ans[0] = accumulate(w.begin(), w.end(), 0LL);
vector<int>par(n), h(n), deg(n);
function<void(int)>dfs;
dfs = [&] (int s){
for(int& i : g[s]){
int d = u[i] ^ v[i] ^ s;
if(d != par[s]){
h[d] = h[par[d] = s] + 1;
dfs(d);
}
}
};
dfs(par[0] = h[0] = 0);
vector<vector<int>>vertex(n);
for(int i = 0; i < n; i++){
vertex[deg[i] = g[i].size()].push_back(i);
}
set<pair<int, int>>s;
for(int k = n - 1; k > 0; k--){
for(int& i : vertex[k]){
s.insert(make_pair(-h[i], i));
}
for(auto& [foo, u] : s){
deg[u] = g[u].size();
}
for(auto& [foo, u] : s){
if(deg[u] > k){
ans[k] += deg[u] - k;
deg[par[u]]--;
}
}
}
return ans;
}
}
namespace sub67{
struct Node{
int cnt, c[2];
ll s;
Node(){
c[cnt = s = 0] = c[1] = -1;
}
};
struct Data{
vector<Node>t;
Data(){
t.push_back(Node());
}
void insert(int x){
for(int i = 29, r = 0; i > -1; i--){
bool N = x >> i & 1;
if(t[r].c[N] == -1){
t[r].c[N] = t.size();
t.push_back(Node());
}
t[r = t[r].c[N]].s += x;
t[r].cnt++;
}
}
void remove(int x){
for(int i = 29, r = 0; i > -1; i--){
t[r = t[r].c[x >> i & 1]].s -= x;
t[r].cnt--;
}
}
ll get_sum(int k){
ll ans = 0;
int r = 0, val = 0;
for(int i = 29; i > -1; i--){
if(t[r].c[0] == -1){
r = t[r].c[1];
val |= 1 << i;
}
else if(t[r].c[1] == -1){
r = t[r].c[0];
}
else if(t[t[r].c[0]].cnt <= k){
ans += t[t[r].c[0]].s;
k -= t[t[r].c[0]].cnt;
r = t[r].c[1];
val |= 1 << i;
}
else{
r = t[r].c[0];
}
}
return ans + ll(val) * k;
}
int get_kth(int k){
int ans = 0;
for(int i = 29, r = 0; i > -1; i--){
if(t[r].c[0] == -1){
r = t[r].c[1];
ans |= 1 << i;
}
else if(t[r].c[1] == -1){
r = t[r].c[0];
}
else if(t[t[r].c[0]].cnt < k){
k -= t[t[r].c[0]].cnt;
r = t[r].c[1];
ans |= 1 << i;
}
else{
r = t[r].c[0];
}
}
return ans;
}
};
Data ds[lim];
bitset<lim>vis;
vector<ll>solve(){
for(int i = 0; i < n; i++){
sort(g[i].begin(), g[i].end(), [&] (int x, int y){
return g[u[x] ^ v[x] ^ i].size() > g[u[y] ^ v[y] ^ i].size();
});
for(int& j : g[i]){
ds[i].insert(w[j]);
}
}
vector<ll>ans(n, 0);
ans[0] = accumulate(w.begin(), w.end(), 0LL);
vector<int>sbd(n);
iota(sbd.begin(), sbd.end(), 0);
sort(sbd.begin(), sbd.end(), [&] (int i, int j){
return g[i].size() > g[j].size();
});
for(int k = n - 1; k > 0; k--){
function<pair<ll, ll>(int, int)>dfs;
dfs = [&] (int s, int p){
vis[s] = true;
int need = int(g[s].size()) - k;
pair<ll, ll>ans = make_pair(0, 0);
vector<int>cache;
for(int& i : g[s]){
int d = u[i] ^ v[i] ^ s;
if(g[d].size() <= k){
break;
}
if(d != p){
ds[s].remove(w[i]);
ds[d].remove(w[i]);
pair<ll, ll>child = dfs(d, s);
if((child.second = min(child.first, child.second) + w[i]) <= child.first){
need--;
ans.first += child.second;
}
else{
ans.first += child.first;
cache.push_back(child.second - child.first);
ds[s].insert(cache.back());
}
}
}
if(need > 0){
ans.second = (ans.first += ds[s].get_sum(need)) - ds[s].get_kth(need);
}
else{
ans.second = ans.first;
}
for(int& x : cache){
ds[s].remove(x);
}
for(int& i : g[s]){
int d = u[i] ^ v[i] ^ s;
if(g[d].size() <= k){
break;
}
if(d != p){
ds[s].insert(w[i]);
ds[d].insert(w[i]);
}
}
return ans;
};
for(int& i : sbd){
if(g[i].size() <= k){
break;
}
vis[i] = false;
}
for(int& i : sbd){
if(g[i].size() <= k){
break;
}
if(!vis[i]){
ans[k] += dfs(i, -1).first;
}
}
}
return ans;
}
}
vector<ll>minimum_closure_costs(int N, vector<int>U, vector<int>V, vector<int>W){
n = N;
swap(u, U);
swap(v, V);
swap(w, W);
for(int i = 0; i + 1 < n; i++){
g[u[i]].push_back(i);
g[v[i]].push_back(i);
}
if(*max_element(u.begin(), u.end()) == 0){
return sub1::solve();
}
if(sub2::check_subtask()){
return sub2::solve();
}
if(n <= 2000){
return sub34::solve();
}
if(*max_element(w.begin(), w.end()) == 1){
return sub5::solve();
}
return sub67::solve();
}
