#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif
const long long mxN = (long long) 1e5 + 5;
const long long LOG = 30;
const long long NODE = mxN * LOG;
const long long INF = (long long) 1e18;
#define BIT(x, i) ((x) >> (i) & 1)
long long N, K;
long long node;
long long dp[mxN][2];
long long deg[mxN];
bool vis[mxN], on[mxN];
long long nxt[NODE][2], cnt[NODE];
long long sum[NODE];
vector<long long> pos[mxN];
vector<pair<long long, long long>> g[mxN], graph[mxN];
void ins(long long u, long long x) {
long long p = u;
for (long long i = LOG - 1; i >= 0; --i) {
long long c = BIT(x, i);
if (!nxt[p][c]) {
nxt[p][c] = ++node;
}
p = nxt[p][c];
sum[p] += x;
cnt[p]++;
}
}
void ers(long long u, long long x) {
long long p = u;
for (long long i = LOG - 1; i >= 0; --i) {
long long c = BIT(x, i);
p = nxt[p][c];
sum[p] -= x;
cnt[p]--;
}
}
long long get(long long u, long long k) {
if (!k) {
return 0;
}
long long res = 0;
long long p = u;
for (long long i = LOG - 1; i >= 0; --i) {
if (cnt[nxt[p][0]] >= k) {
p = nxt[p][0];
} else {
k -= cnt[nxt[p][0]];
res += sum[nxt[p][0]];
p = nxt[p][1];
}
}
return res + k * (sum[p] / cnt[p]);
}
long long rt;
void dfs(long long u) {
dp[u][0] = dp[u][1] = INF;
vis[u] = true;
long long s = 0;
vector<long long> delta;
for (auto [v, w] : graph[u]) {
if (!vis[v]) {
dfs(v);
delta.emplace_back(dp[v][1] - dp[v][0] + w);
s += dp[v][0];
}
}
sort(delta.begin(), delta.end());
for (long long i = 1; i < (long long) delta.size(); ++i) {
delta[i] += delta[i - 1];
}
long long need = deg[u] - K;
long long m = (long long) delta.size(), tm = deg[u] - m - (u != rt);
for (long long i = 0; i <= min(m, need); ++i) {
if (i <= need - 1 && need - 1 - i <= tm) {
dp[u][1] = min(dp[u][1], s + (i ? delta[i - 1] : 0LL) + get(u, need - 1 - i));
}
if (need - i <= tm) {
dp[u][0] = min(dp[u][0], s + (i ? delta[i - 1] : 0LL) + get(u, need - i));
}
}
}
vector<long long> ver;
void turn_on(long long u) {
on[u] = true;
ver.emplace_back(u);
for (auto [v, w] : g[u]) {
if (on[v]) {
ers(v, w);
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);
} else {
ins(u, w);
}
}
}
std::vector<long long> minimum_closure_costs(int n, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
N = n;
node = N;
vector<long long> res(N);
for (long long i = 0; i < N; ++i) {
U[i]++;
V[i]++;
deg[U[i]]++;
deg[V[i]]++;
g[U[i]].emplace_back(V[i], W[i]);
g[V[i]].emplace_back(U[i], W[i]);
}
for (long long i = 1; i <= N; ++i) {
pos[deg[i]].emplace_back(i);
}
for (long long i = N - 1; i >= 0; --i) {
K = i;
for (long long u : pos[i + 1]) {
turn_on(u);
}
for (long long u : ver) {
if (!vis[u]) {
rt = u;
dfs(u);
res[i] += dp[u][0];
}
}
for (long long u : ver) {
vis[u] = false;
}
}
return res;
}
