#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 100005;
class DisjointSet {
private:
vector<int> lab;
public:
DisjointSet(int _n = 0) {
lab.assign(_n + 7, -1);
}
int find(int u) {
return (lab[u] < 0) ? u : (lab[u] = find(lab[u]));
}
bool join(int u, int v) {
u = find(u), v = find(v);
if(u == v)
return (false);
if(lab[u] > lab[v])
swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return (true);
}
} dsu;
struct Edge {
int u, v, w;
} edge[MAXN];
vector<ii> adj[MAXN];
ll dp[MAXN][2], f[2003][2003][2];
int sz[MAXN], pa[MAXN], deg[MAXN], numNode;
vector<ll> sub1(void) {
sort(edge, edge + numNode - 1, [](const Edge &a, const Edge &b) {
return (a.w > b.w);
});
vector<ll> ans;
ll sumCost(0);
for (int i = 0; i < numNode - 1; ++i)
sumCost += edge[i].w;
for (int i = 0; i < numNode; ++i) {
ans.push_back(sumCost);
sumCost -= edge[i].w;
}
return ans;
}
vector<ll> sub2(void) {
vector<ll> ans;
ll sumCost(0);
dp[0][0] = dp[0][1] = 0;
for (int i = 0; i < numNode - 1; ++i) {
sumCost += edge[i].w;
dp[i + 1][0] = max(dp[i][1], dp[i][0]);
dp[i + 1][1] = dp[i][0] + edge[i].w;
}
ans.push_back(sumCost);
ans.push_back(sumCost - max(dp[numNode - 1][0], dp[numNode - 1][1]));
for (int i = 2; i < numNode; ++i)
ans.push_back(0);
return ans;
}
typedef pair<ll, ll> pll;
void dfsDP(int u) {
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it].fi), w(adj[u][it].se);
if(v != pa[u]) {
pa[v] = u;
dfsDP(v);
f[u][0][0] += f[v][0][0];
f[u][0][1] += f[v][0][1];
}
}
for (int i = 1; i < numNode; ++i) {
vector<pll> p;
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it].fi), w(adj[u][it].se);
if(v != pa[u])
p.push_back(pll(max(f[v][i - 1][1], f[v][i][0]) + w, max(f[v][i][0], f[v][i][1])));
}
sort(p.begin(), p.end(), [](const pll &a, const pll &b) {
return a.fi - a.se > b.fi - b.se;
});
f[u][i][0] = -1e18;
for (int j = 0; j < sz(p); ++j) {
f[u][i][0] = max(f[u][i][0] + (j < i ? max(p[j].fi, p[j].se) : p[j].se), (j < i ? f[u][i][1] + p[j].se : 0LL));
f[u][i][1] += (j < i) ? max(p[j].fi, p[j].se) : p[j].se;
}
if(sz(p) < i)
f[u][i][0] = max(f[u][i][0], f[u][i][1]);
}
}
vector<ll> sub4(void) {
ll sumCost(0);
for (int i = 0; i + 1 < numNode; ++i) {
int u(edge[i].u), v(edge[i].v), w(edge[i].w);
adj[u].push_back(ii(v, w));
adj[v].push_back(ii(u, w));
sumCost += w;
}
pa[0] = -1;
dfsDP(0);
vector<ll> ans;
for (int i = 0; i < numNode; ++i) {
ans.push_back(sumCost - max(f[0][i][0], f[0][i][1]));
//cout << max(f[1][i][0], f[1][i][1]) << " \n"[i + 1 == numNode];
}
return ans;
}
vector<ll> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W) {
numNode = _N;
bool check_sub1(1), check_sub2(1);
for (int i = 0; i + 1 < numNode; ++i) {
edge[i] = {_U[i], _V[i], _W[i]};
if(edge[i].u > edge[i].v)
swap(edge[i].u, edge[i].v);
check_sub1 &= (edge[i].u == 0);
check_sub2 &= (edge[i].u == i && edge[i].v == i + 1);
}
/*if(check_sub1)
return sub1();
if(check_sub2)
return sub2();*/
if(numNode <= 2000)
return sub4();
return {-1};
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "roads"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<int> u, v, w;
int n;
cin >> n;
u.resize(n - 1), v.resize(n - 1), w.resize(n - 1);
for (int i = 0; i + 1 < n; ++i) {
cin >> u[i] >> v[i] >> w[i];
}
vector<ll> ans = minimum_closure_costs(n, u, v, w);
cout << "ANSWER: ";
for (int it = 0; it < sz(ans); ++it)
cout << ans[it] << ' '; cout << '\n';
return 0;
}
#endif // Nhoksocqt1
