#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e5 + 5;
int n, k;
int deg[MXN];
int used[MXN];
vector<array<long long, 3>> adj[MXN];
array<int, 2> dfs(int a, int p, int cur, long long sum)
{
if (sum > 0 && (cur == 0 || deg[a] < k)) return {a, sum};
for (auto &[v, w, idx] : adj[a])
{
if (v == p) continue;
if (used[idx] == cur)
{
if (!cur)
{
array<int, 2> x = dfs(v, a, cur ^ 1, sum + w);
if (x[0] != -1)
{
deg[a]++, deg[v]++;
used[idx] ^= 1;
return x;
}
}
else
{
array<int, 2> x = dfs(v, a, cur ^ 1, sum - w);
if (x[0] != -1)
{
deg[a]--, deg[v]--;
used[idx] ^= 1;
return x;
}
}
}
}
return {-1, 0};
}
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W)
{
n = N;
long long all = 0;
for (int i = 0; i < U.size(); i++)
{
long long u = U[i], v = V[i], w = W[i];
adj[u].push_back({v, w, i});
adj[v].push_back({u, w, i});
all += w;
}
long long res = 0;
vector<long long> v;
for (k = 0; k < n; k++)
{
int F = 1;
while (F)
{
F = 0;
long long S = 0;
for (int i = 0; i < n; i++)
{
if (deg[i] == k) continue;
S += dfs(i, i, 0, 0)[1];
}
res += S;
F = (S > 0);
}
v.push_back(all - res);
}
return v;
}
