#include "roads.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
const ld PI = 3.1415926535;
const int N = 5e5+10;
const int M = 1e4 + 5;
int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 467743;
ll dp[N][2];
int n, k;
vector<pair<ll, ll>> g[N];
void dfs(int v, int p, int w){
dp[v][0] = dp[v][1] = 0;
for(auto u : g[v])
if(u.F != p)
dfs(u.F, v, u.S);
vector<pair<ll, pll>> vs = {};
for(auto u : g[v]){
if(u.F != p){
vs.pb({dp[u.F][1] - dp[u.F][0], {dp[u.F][1], dp[u.F][0]}});
}
}
sort(all(vs));
reverse(all(vs));
for(int i = 0; i < min(k, sz(vs)); i++){
if(vs[i].F > 0){
dp[v][0] += vs[i].S.F;
}else{
dp[v][0] += vs[i].S.S;
}
}
for(int i = min(k, sz(vs)); i < sz(vs); i++){
dp[v][0] += vs[i].S.S;
}
for(int i = 0; i < min(k - 1, sz(vs)); i++){
if(vs[i].F > 0){
dp[v][1] += vs[i].S.F;
}else{
dp[v][1] += vs[i].S.S;
}
}
for(int i = min(k - 1, sz(vs)); i < sz(vs); i++){
dp[v][1] += vs[i].S.S;
}
dp[v][1] += w;
}
vector<long long> minimum_closure_costs(int _n, vector<int> U, vector<int> V, vector<int> W) {
n = _n;
vector<ll> ans(n, 0);
for(int i = 0; i < n - 1; i++){
U[i]++;
V[i]++;
g[V[i]].pb({U[i], W[i]});
g[U[i]].pb({V[i], W[i]});
ans[0] += W[i];
}
k = 1;
for(; k < n; k++){
dfs(1, -1, 0);
ans[k] = ans[0] - dp[1][0];
}
return ans;
}
/*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) {
std::cin >> 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;
}*/
