#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const ll INF = 1e18;
const ll mod = 1e9 + 7;
#include "roads.h"
void solve(ll cur, vvp &graph, vp &res, ll k, vb &visited) //first = normal, second = without parent
{
if (visited[cur]) return;
visited[cur] = true;
for (auto x : graph[cur]) solve(x.f, graph, res, k, visited);
ll needToRemove = max(0ll, (ll)graph[cur].size() - k);
ll needToRemove2 = max(0ll, needToRemove - 1);
v add1, add2;
ll sum = 0;
for (auto x : graph[cur])
{
if (res[x.f].f == -1)
{
add1.pb(x.s); continue;
}
add1.pb(res[x.f].s - res[x.f].f + x.s);
add2.pb(res[x.f].s - res[x.f].f + x.s);
sum += res[x.f].f;
}
sort(all(add1)); sort(all(add2));
res[cur] = p(sum, sum);
for (ll i = 0; i < needToRemove; i++) res[cur].f += add1[i];
for (ll i =0 ; i < needToRemove2; i++) res[cur].s += add2[i];
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vvp graph(N);
for (ll i = 0; i < N - 1; i++)
{
graph[U[i]].eb(V[i],W[i]);
graph[V[i]].eb(U[i],W[i]);
}
vector<long long> res(N, -1);
ll sum = 0;
for (auto x : W) sum += x;
res[0] = sum;
for (ll i =1; i < N; i++)
{
vb visited(N, false);
vp dp(N, p(-1, -1));
solve(0, graph, dp, i, visited);
res[i] = dp[0].f;
}
return res;
}
/*
int main() {
int N;
assert(1 == scanf("%d", &N));
std::vector<int> U(N - 1), V(N - 1), W(N - 1);
for (int i = 0; i < N - 1; ++i) {
assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
}
std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
if (i > 0) {
printf(" ");
}
printf("%lld",closure_costs[i]);
}
printf("\n");
return 0;
}
/**/
