#include "roads.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int NMAX = 100005;
typedef long long LL;
constexpr LL INF = 1LL * 1e15;
struct muchie {
int x, y;
LL cost;
};
muchie E[NMAX];
vector <int> G[NMAX];
LL dp[NMAX][2];
LL aux[NMAX];
void Dfs (int k, int Node, int dad = -1) {
for (auto it : G[Node]) {
int to = (E[it].x == Node ? E[it].y : E[it].x);
if (to == dad) continue;
Dfs(k, to, Node);
}
for (int i = 0; i <= k; ++ i )
aux[i] = 0;
aux[0] = 0;
int grad = 0;
vector <LL> V;
LL sum = 0;
for (auto it : G[Node]) {
int to = (E[it].x == Node ? E[it].y : E[it].x);
if (to == dad) continue;
++ grad;
V.push_back(dp[to][1] - dp[to][0]);
sum += dp[to][0];
}
dp[Node][0] = INF;
dp[Node][1] = INF;
sort(V.begin(), V.end());
if (k > 0) {
dp[Node][0] = sum;
for (int i = 0; i < max(0, grad - k + 1); ++ i )
dp[Node][0] += V[i];
}
if (dad == -1) {
dp[Node][1] = sum;
for (int i = 0; i < max(0, grad - k); ++ i )
dp[Node][1] += V[i];
}
for (auto it : G[Node]) {
int to = (E[it].x == Node ? E[it].y : E[it].x);
if (to != dad) continue;
dp[Node][1] = sum + E[it].cost;
for (int i = 0; i < max(0, grad - k); ++ i )
dp[Node][1] += V[i];
break;
}
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
for (int i = 1; i < N; ++ i ) {
E[i] = {U[i-1], V[i-1], 1LL * W[i-1]};
G[U[i-1]].push_back(i);
G[V[i-1]].push_back(i);
}
vector <LL> ans;
for (int k = 0; k < N; ++ k ) {
Dfs(k, 0);
ans.push_back(dp[0][1]);
}
return ans;
}
