#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
namespace{
const ll maxn = 1e5+5;
const ll inf = 1ll<<60;
int n;
vector<pii> g[maxn];
vector<pii> ag[maxn];
vector<int> par(maxn);
}
int fin(int a){
if (par[a] == a) return a;
return par[a] = fin(par[a]);
}
void merg(int a, int b){
a = fin(a); b = fin(b);
par[a] = b;
}
map<pii, int> mp;
int dp[maxn][2]; // subtree of u, whether alr matches with a child
pii pp[maxn];
vector<bool> occ(maxn);
vector<pii> poo;
void dfs(int u, int pre){
occ[u] = 1;
dp[u][0] = dp[u][1] = 0;
pp[u] = {-inf, -1};
for (auto e:ag[u]){
if (e.f == pre) continue;
dfs(e.f, u);
dp[u][0] += max(dp[e.f][1], dp[e.f][0]);
dp[u][1] += max(dp[e.f][1], dp[e.f][0]);
if (pp[u].f < e.s + dp[e.f][0] - max(dp[e.f][1], dp[e.f][0])){
pp[u].f = e.s + dp[e.f][0] - max(dp[e.f][1], dp[e.f][0]);
pp[u].s = e.f;
}
}
dp[u][1] += pp[u].f;
}
void dfs2(int u, int pre, bool wh){
if (!wh){
for (auto e:ag[u]){
if (e.f == pre) continue;
if (dp[e.f][0] > dp[e.f][1]) dfs2(e.f, u, 0);
else dfs2(e.f, u, 1);
}
}
else{
poo.pb({pp[u].s, u});
for (auto e:ag[u]){
if (e.f == pre) continue;
if (pp[u].s == e.f){
dfs2(e.f, u, 0);
}
else{
if (dp[e.f][0] > dp[e.f][1]) dfs2(e.f, u, 0);
else dfs2(e.f, u, 1);
}
}
}
}
std::vector<long long> minimum_closure_costs(signed N, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
n = N;
int sm = 0;
REP(i, n-1){
sm += W[i];
g[U[i]].pb({V[i], W[i]});
g[V[i]].pb({U[i], W[i]});
mp[{U[i], V[i]}] = i;
mp[{V[i], U[i]}] = i;
}
vector<bool> ban(n-1);
REP(i, n) par[i] = i;
vector<int> ret;
ret.pb(sm);
REP(t, n-1){
REP(i, n) ag[i].clear();
REP(i, n) occ[i] = 0;
REP(i, n-1){
if (!ban[i]){
ag[U[i]].pb({V[i], W[i]});
ag[V[i]].pb({U[i], W[i]});
}
}
poo.clear();
REP(i, n) if (!occ[i]) {
dfs(i, -1);
if (dp[i][0] > dp[i][1]) dfs2(i, -1, 0);
else dfs2(i, -1, 1);
sm -= max(dp[i][0], dp[i][1]);
}
for (auto ee:poo){
ban[mp[{ee.f, ee.s}]] = 1;
}
ret.pb(sm);
}
return ret;
}
