#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
const int nax = 100 * 1000 + 10;
int n;
vector<tuple<int,int,int>>edges;
int cnt[nax];
vi weak[nax];
bool taken[nax];
vector<ll> minimum_closure_costs(int N, vi U, vi V, vi W) {
n = N;
for(int i = 0; i < n - 1; ++i) {
edges.emplace_back(W[i], U[i], V[i]);
}
sort(edges.begin(), edges.end());
vector<ll>ans(n);
for(int k = 0; k < n; ++k) {
ll res = 0;
for(auto [c, a, b] : edges) {
cnt[a]++, cnt[b]++;
}
int id = 1;
for(auto [c, a, b] : edges) {
if(cnt[a] > k && cnt[b] > k) {
cnt[a]--, cnt[b]--;
res += c;
taken[id] = true;
} else if(cnt[a] > k) {
cnt[a]--;
weak[a].PB(c);
taken[id] = true;
} else if(cnt[b] > k) {
cnt[b]--;
weak[b].PB(c);
taken[id] = true;
}
id++;
}
id = 1;
for(auto [c, a, b] : edges) {
if(!taken[id]) {
if(!weak[a].empty() && !weak[b].empty() && weak[a].back() + weak[b].back() > c) {
res += c;
weak[a].pop_back();
weak[b].pop_back();
}
}
id++;
}
for(int i = 0; i < n; ++i) {
cnt[i] = 0;
for(int c : weak[i]) res += c;
weak[i].clear();
taken[i] = false;
}
ans[k] = res;
}
return ans;
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//cin >> n;
//vi u(n-1), v(n-1), w(n-1);
//for(int i = 0; i < n-1; ++i) cin >> u[i] >> v[i] >> w[i];
//auto vec = minimum_closure_costs(n, u, v, w);
//for(auto x : vec) cout << x << " ";
//}
