#include <bits/stdc++.h>
using namespace std;
template<class T>
using ii = array<T, 2>;
using ll = long long;
using vi = vector<int>;
const int Z = 1e5;
const ll INF = 1e18;
struct BIT {
vi a;
vector<ii<int>> vals;
vector<ll> b;
int n, sz {};
void addVal(ii<int> v) {
vals.push_back(v);
}
void init() {
sort(begin(vals), end(vals));
n = size(vals) + 1;
b.resize(n);
a.resize(n);
}
void insert(ii<int> v) {
int i = 1 + lower_bound(begin(vals), end(vals), v) - begin(vals);
for(++sz; i<n; i+=i&-i) {
a[i] += 1;
b[i] += v[0];
}
}
ll query(int v) {
if(v > sz) return INF;
int i = 0; ll s = 0;
for(int j = 1<<17; j /= 2; ) if(i+j < n && a[i+j] <= v) {
i += j;
v -= a[i];
s += b[i];
}
return s;
}
} s[Z];
int deg[Z], k;
bool vis[Z];
vector<ii<int>> g[Z];
#define sum(X, Y) (X >= INF || Y >= INF ? INF : X + Y)
ii<ll> dfs(int u) {
ii<ll> res {INF, INF};
vis[u] = 1;
vector<ii<ll>> x;
for(auto [v, w] : g[u]) if(!vis[v]) {
x.push_back(dfs(v));
x.back()[1] = sum(x.back()[1], w);
}
ll cost {};
for(auto &[i, j] : x) {
cost += i;
i -= j;
}
sort(rbegin(x), rend(x));
for(int i = 0; ; ++i) {
for(int j : {0, 1})
res[j] = min(res[j], sum(cost, s[u].query(max(0, (deg[u] - k) - i - j))));
if(i == int(size(x))) break;
cost -= x[i][0];
}
return res;
}
vector<ll> minimum_closure_costs(int N, vi U, vi V, vi W) {
for(int i = 0; i + 1 < N; ++i) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
++deg[U[i]], ++deg[V[i]];
}
vector<ii<int>> a;
vector<ll> res(N);
for(int u = 0; u < N; ++u) {
sort(begin(g[u]), end(g[u]), [&](auto i, auto j) {
return deg[i[0]] > deg[j[0]];
});
a.push_back({int(size(g[u])), u});
for(auto [v, w] : g[u])
s[u].addVal({w, v});
s[u].init();
}
sort(rbegin(a), rend(a));
for(k = 0; k < N; ++k) {
while(!empty(a) && a.back()[0] < k)
a.pop_back();
for(auto [_d, u] : a) {
while(!empty(g[u]) && deg[g[u].back()[0]] < k) {
s[u].insert({g[u].back()[1], g[u].back()[0]});
g[u].pop_back();
}
vis[u] = 0;
}
for(auto [_d, u] : a)
if(!vis[u]) res[k] += dfs(u)[0];
}
return res;
}
