#include <bits/stdc++.h>
template<class T>
void chkmin(T &x, const T &y) {
if (x > y) x = y;
}
using ll = long long;
struct sgt {
struct line {
ll k, b;
ll eval(ll x) { return k * x + b; }
};
static int const BUF = 2e6;
static line tr[BUF];
static int ls[BUF], rs[BUF], ntot;
int rt;
ll l, r;
void insert(int &i, ll l, ll r, line li) {
if (!i) return tr[i = ++ntot] = li, void();
auto mid = (l + r) >> 1;
if (li.eval(mid) < tr[i].eval(mid)) std::swap(li, tr[i]);
if (li.eval(l) < tr[i].eval(l)) insert(ls[i], l, mid, li);
if (li.eval(r) < tr[i].eval(r)) insert(rs[i], mid + 1, r, li);
}
ll query(int i, ll l, ll r, ll p) {
if (!i) return 1e18;
auto mid = (l + r) >> 1;
if (p <= mid) return std::min(query(ls[i], l, mid, p), tr[i].eval(p));
else return std::min(query(rs[i], mid + 1, r, p), tr[i].eval(p));
}
sgt(ll l, ll r) : rt(0), l(l), r(r) {}
void insert(line li) { insert(rt, l, r, li); }
auto query(ll p) { return query(rt, l, r, p); }
};
sgt::line sgt::tr[sgt::BUF];
int sgt::ls[sgt::BUF], sgt::rs[sgt::BUF], sgt::ntot;
std::vector<ll> travel(std::vector<ll> a, std::vector<int> b,
std::vector<int> u, std::vector<int> v,
std::vector<int> w) {
int n = a.size();
a.insert(a.begin(), 0), b.insert(b.begin(), 0);
std::vector<std::vector<std::pair<int, int>>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
++u[i], ++v[i];
g[u[i]].emplace_back(v[i], w[i]);
g[v[i]].emplace_back(u[i], w[i]);
}
std::vector<std::vector<std::pair<int, ll>>> h(n + 1);
std::vector<int> vis(n + 1);
auto build = [&](auto &self, int u) -> void {
int tot = 0;
auto dfs1 = [&](auto &self, int u, int ff) -> void {
tot += 1;
for (auto [v, w] : g[u])
if (v != ff && !vis[v]) self(self, v, u);
};
int rt = 0;
auto dfs2 = [&](auto &self, int u, int ff) -> int {
int ret = 1;
for (auto [v, w] : g[u])
if (v != ff && !vis[v]) ret += self(self, v, u);
if (ret * 2 >= tot && !rt) rt = u;
return ret;
};
dfs1(dfs1, u, 0), dfs2(dfs2, u, 0);
auto dfs3 = [&](auto &self, int u, int ff, ll d) -> void {
h[u].emplace_back(rt, d);
for (auto [v, w] : g[u])
if (v != ff && !vis[v])
self(self, v, u, d + w);
};
dfs3(dfs3, rt, 0, 0);
vis[rt] = 1;
for (auto [v, w] : g[rt])
if (!vis[v])
self(self, v);
};
build(build, 1);
cpp_dump(h);
std::vector<sgt> tr(n + 1, sgt(0, 1e11));
auto query = [&](int u) {
ll ret = 1e18;
for (auto [id, dis] : h[u])
chkmin(ret, tr[id].query(dis));
return ret;
};
auto update = [&](int u, ll d) {
for (auto [id, dis] : h[u])
tr[id].insert({b[u], a[u] + d + b[u] * dis});
};
std::vector<int> id(n - 1);
std::iota(id.begin(), id.end(), 2);
std::sort(id.begin(), id.end(), [&](int u, int v) { return b[u] < b[v]; });
update(1, 0);
for (int i : id) {
auto d = query(i);
update(i, d);
}
std::vector<ll> ret;
for (int i = 2; i <= n; i++)
ret.push_back(query(i));
return ret;
}