//wtf is this
#include "roads.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
const ll INFL = 1e18;
const ll BIG = 1e10;
class ST {
private:
struct NO {
NO *lf,*rt;
ll su, kt;
NO() {
su = kt = 0;
lf = rt = nullptr;
}
NO(ll val) {
su = val;
kt = 1;
lf = rt = nullptr;
}
};
ll get(NO* no, ll l, ll r, ll q) {
if(no->kt < q) {
return INFL;
}
if(q <= 0) {return 0;}
if(l == r) {
return l*q;
}
ll m = (l+r)/2;
ll ans = 0;
if(no->lf != nullptr) {
if(no->lf->kt >= q) {
return get(no->lf,l,m,q);
} else {
ans += no->lf->su;
q -= no->lf->kt;
}
}
if(no->rt != nullptr) {
ans += get(no->rt,m+1,r,q);
}
return ans;
}
vector<NO*> st;
ll subz,sukt;
void ens(NO* no, ll l, ll r, ll val, ll num) {
no->su += val*num;
no->kt += num;
if(l == r) {
return;
}
ll m = (l+r)/2;
if(val <= m) {
if(no->lf == nullptr) {
NO* nx = new NO();
st.push_back(nx);
no->lf = nx;
}
ens(no->lf,l,m,val,num);
} else {
if(no->rt == nullptr) {
NO* nx = new NO();
st.push_back(nx);
no->rt = nx;
}
ens(no->rt,m+1,r,val,num);
}
}
ll ls, rs;
public:
ST(ll ls_, ll rs_) {
ls = ls_;
rs = rs_;
st.push_back(new NO());
sukt = subz = 0;
}
ll get(ll q) {
ll ad = subz;
q -= sukt;
return ad+get(st.front(),ls,rs,q);
}
void ens(ll val) {
if(val < 0) {
subz += val;
sukt++;
} else {
ens(st.front(),ls,rs,val,1);
}
}
void del(ll val) {
if(val < 0) {
subz -= val;
sukt--;
} else {
ens(st.front(),ls,rs,val,-1);
}
}
};
vl degs;
vector<vector<ii>> h;
vector<ST> wos;
vl lov;
pl dfs(ll u, ll p, int deg) {
lov[u] = deg;
ll ad = 0;
vector<pl> difs;
ll rek = degs[u]-deg;
for(int i=0;i<h[u].size();i++) {
int v = h[u][i].first;
ll c = h[u][i].second;
if(v == p) {
wos[u].del(c);
difs.emplace_back(c,-INFL);
continue;
}
pl res = dfs(v,u,deg);
if(res.first >= INFL) {
difs.emplace_back(c,-INFL);
wos[u].del(c);
rek--;
ad += c+res.second;
} else {
difs.emplace_back(c,c+res.second-res.first);
wos[u].del(c);
wos[u].ens(c+res.second-res.first);
ad += res.first;
}
}
pl ans = {wos[u].get(rek)+ad,wos[u].get(rek-1)+ad};
for(const auto& it: difs) {
if(it.second > -INFL) {
wos[u].del(it.second);
}
wos[u].ens(it.first);
}
return ans;
}
vector<vector<ii> > g;
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
ll sus = 0;
int M = U.size();
degs.assign(N,0);
g.resize(N);
for(int i=0;i<M;i++) {
int u = U[i];
int v = V[i];
int c = W[i];
g[u].emplace_back(v,c);
g[v].emplace_back(u,c);
sus += c;
degs[u]++;
degs[v]++;
}
vector<ii> ord;
for(int i=0;i<N;i++) {
ord.emplace_back(degs[i],i);
}
sort(ord.begin(),ord.end());
vi rord(N);
for(int i=0;i<ord.size();i++) {
rord[ord[i].second] = i;
}
int pt = N-1;
for(int i=0;i<N;i++) {
wos.emplace_back(0,BIG);
}
for(int i=0;i<N;i++) {
for(const auto& eg: g[i]) {
int c = eg.second;
wos[i].ens(c);
}
}
h.resize(N);
lov.assign(N,N);
vector<ll> ans(N);
for(int dv=N-1;dv>=1;dv--) {
while(pt >= 0 && degs[ord[pt].second] > dv) {
int u = ord[pt].second;
for(const auto& eg: g[u]) {
int v = eg.first;
int c = eg.second;
if(rord[v] > rord[u]) {
h[u].emplace_back(v,c);
h[v].emplace_back(u,c);
}
}
pt--;
}
ll res = 0;
for(int i=N-1;i>pt;i--) {
int u = ord[i].second;
if(lov[u] > dv) {
res += dfs(u,u,dv).first;
}
}
ans[dv] = res;
}
ans[0] = sus;
return ans;
}
