#include "roads.h"
#include <iostream>
#include <vector>
#include <cmath>
#include<map>
#include <algorithm>
#include <iomanip>
#include <string>
#include<stack>
#include <set>
#include <queue>
#include <chrono>
#include<array>
#include<bitset>
#include<unordered_map>
#include<random>
#include<cassert>
#include<cstring>
using namespace std;
using ll = long long;
using db = double;
const float pi = 3.14159265359;
#define V vector
#define VI V<int>
#define P pair<int,int>
#define rep(i, a, b, step) for (int i = int(a); i <= int(b); i += step)
#define repl(i,a,b,step) for (int i = int(a); i >= int(b); i -= step)
#define prime(n) [](int x) { for (int i = 2; i *1ll* i <= x; ++i) if (x % i == 0) return false; return x > 1; }(n)
#define printall(container, ch) for (const auto& elem : container) { std::cout << elem << ch; } std::cout << std::endl;
#define sn << '\n'
#define ed << endl
#define sz size()
#define print cout <<
#define debug(x) cerr<< #x << " = " << x sn;
#define mpII map<int,int>
#define mine min_element
#define maxe max_element
#define all(v) begin(v), end(v)
#define txt freopen("snakes.in", "r", stdin); freopen("snakes.out", "w", stdout)
#define MEX(a) [](VI a){set<int>elem;for(auto&i:a)elem.insert(i);int ret=0;while(elem.count(ret))ret++;return ret;}(a)
#define pb push_back
#define pq priority_queue
#define rev reverse
#define nuyn(a) a.erase(unique(all(a)), end(a))
#define nx next_permutation
#define pk pop_back()
#define START print "Start" sn
#define END print "End" sn
#define ff first
#define ss second
#define ts to_string
#define ub upper_bound
#define mk make_pair
#define lb lower_bound
#define testcase int t;cin>>t;while(t--)solution();
const int N = 2e3;
const ll inf = 1e15;
V<P> graph[N];
ll dp[N][2];
int k;
void dfs(int u, int p) {
if (graph[u].sz == 1 and u != 1) {
dp[u][0] = dp[u][1] = 0;
return;
}
int need, cnt = 0;
ll sum1 = 0, sum2;
V<ll>sm;
for (auto& i : graph[u])if (i.ff != p) {
dfs(i.ff, u);
if (dp[i.ff][0] == inf) {
sum1 += dp[i.ff][1] + i.ss;
cnt++;
}
else {
sum1 += dp[i.ff][0];
sm.pb(min(dp[i.ff][0], dp[i.ff][1]) + i.ss - dp[i.ff][0]);
}
}
sort(all(sm));
rep(K, k, k + 1, 1) {
need = max(0, (int)graph[u].sz - K - cnt);
if (need > sm.sz)dp[u][K - k] = inf;
else {
sum2 = sum1;
rep(i, 0, need - 1, 1)sum2 += sm[i];
dp[u][K - k] = min(dp[u][K - k], sum2);
}
}
dp[u][1] = min(dp[u][1], dp[u][0]);
}
std::vector<long long> minimum_closure_costs(int n, std::vector<int> u, std::vector<int> v, std::vector<int> w) {
V<ll>ans(n);
rep(i, 0, n - 2, 1) {
graph[u[i]].pb({ v[i],w[i] });
graph[v[i]].pb({ u[i],w[i] });
ans[0] += w[i];
}
rep(K, 1, n - 1, 1) {
k = K;
rep(i, 0, n - 1, 1)dp[i][0] = dp[i][1] = inf;
dfs(0, 0);
ans[K] = dp[0][0];
}
return ans;
}
