//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
#include "roads.h"
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
void dfs(ll v, ll p, vector<vector<pair<ll, ll>>>& tree, vector<pair<vector<ll>, vector<ll>>>& dp) {
ll rpc = INF32;
ll nx = 0;
ll ms = 0;
for (auto[a, b] : tree[v]) {
if (a == p) {
rpc = b;
} else {
dfs(a, v, tree, dp);
assign_max(ms, (ll)dp[a].first.size());
}
}
for (auto[a, b] : tree[v]) {
if (a != p) {
if (dp[a].first.size() == ms) {
swap(dp[a], dp[v]);
nx = b;
break;
}
}
}
while (dp[v].first.size() < tree[v].size()) {
dp[v].first.push_back(0);
}
while (dp[v].second.size() < tree[v].size()) {
dp[v].second.push_back(dp[v].first[dp[v].second.size()] + nx);
}
while (dp[v].second.size() > tree[v].size()) {
dp[v].second.pop_back();
}
vector<pair<ll, ll>> sons;
if (nx != 0) {
sons.emplace_back(v, nx);
}
for (auto[a, b] : tree[v]) {
if (!dp[a].first.empty()) {
sons.emplace_back(a, b);
for (ll j = tree[v].size(); j < dp[a].first.size(); j++) {
dp[v].first[j] += dp[a].first[j];
}
}
}
multiset<ll> all;
ll ns = 0;
for (ll i = 0; i < tree[v].size(); i++) {
vector<pair<ll, ll>> nsons;
vector<ll> nall;
ll na = 0;
for (auto[a, b] : sons) {
if (dp[a].first.size() > i) {
na += dp[a].first[i];
}
if (dp[a].second.size() > i) {
nall.push_back(dp[a].second[i] - dp[a].first[i]);
nsons.emplace_back(a, b);
} else {
all.insert(b);
ns += b;
//nall.push_back(b);
//nsons.emplace_back(a, b);
}
}
while (all.size() > (tree[v].size() - i)) {
ns -= *all.rbegin();
all.erase(all.find(*all.rbegin()));
}
auto it = all.rbegin();
ll x = all.size();
sort(nall.begin(), nall.end());
na += ns;
ll mx = 0;
for (auto j : nall) {
if (x < (tree[v].size() - i)) {
assign_max(mx, j);
x++;
na += j;
} else {
if (it != all.rend() && *it > j) {
na += j;
na -= *it;
it++;
assign_max(mx, j);
}
}
}
if (it != all.rend()) {
assign_max(mx, *it);
}
if (i == 0) {
mx = 0;
}
dp[v].first[i] = na;
dp[v].second[i] = na - mx + rpc;
assign_min(dp[v].first[i], dp[v].second[i]);
sons = nsons;
}
}
vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
vector<vector<pair<ll, ll>>> tree(n);
for (ll i = 0; i < u.size(); i++) {
tree[u[i]].emplace_back(v[i], w[i]);
tree[v[i]].emplace_back(u[i], w[i]);
}
vector<pair<vector<ll>, vector<ll>>> dp(n);
dfs(0, 0, tree, dp);
dp[0].first.resize(n, 0);
return dp[0].first;
}
#ifdef LOCAL
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;
}
#endif
