#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const int N = 1e5 + 5, inf = 1e18;
int s[N], v[N], dp[N];
vector<vector<pair<int, int>>> adj;
// To get an instance : node *root = EMPTY;
typedef pair<int, int> line;
int start_x = 0, end_x = 1e18;
int sub(const line &l, int x) {
return l.first * x + l.second;
}
double inter(const line &l1, const line &l2) {
return (double) (l2.second - l1.second) / (l1.first - l2.first);
}
extern struct node *const EMPTY;
struct change {
node **ptr;
node *old;
line l;
};
vector<change> history;
struct node {
line l;
node *lf, *rt;
node() : l({0, 0}), lf(this), rt(this) {}
node(line l) : l(l), lf(EMPTY), rt(EMPTY) {}
};
node *const EMPTY = new node;
void insert(line l, node *&cur, int ns = start_x, int ne = end_x) {
history.push_back({&cur, cur, (cur ? cur->l : line{0, -inf})});
if (cur == EMPTY) {
cur = new node(l);
return;
}
if (l.first == cur->l.first) {
cur->l = max(cur->l, l);
return;
}
double x = inter(l, cur->l);
if (x < ns || x > ne) {
if (sub(l, ns) > sub(cur->l, ns))
cur->l = l;
return;
}
int mid = ns + (ne - ns) / 2;
if (x <= mid) {
if (sub(l, ne) > sub(cur->l, ne))
swap(l, cur->l);
insert(l, cur->lf, ns, mid);
} else {
if (sub(l, ns) > sub(cur->l, ns))
swap(l, cur->l);
insert(l, cur->rt, mid + 1, ne);
}
}
int query(int x, node *cur, int ns = start_x, int ne = end_x) {
if (x < ns || x > ne)
return LLONG_MIN;
int ret = sub(cur->l, x);
if (ns == ne)
return ret;
int mid = ns + (ne - ns) / 2;
if (x <= mid)
return max(ret, query(x, cur->lf, ns, mid));
else
return max(ret, query(x, cur->rt, mid + 1, ne));
}
node *T = EMPTY;
void go(int u, int p, int d) {
if (p)
dp[u] = d * v[u] + s[u] - query(v[u], T);
int sz = history.size();
insert({d, -dp[u]}, T);
for (auto [x, add]: adj[u]) {
if (x == p)continue;
go(x, u, d + add);
}
while (history.size() > sz) {
auto [ptr, old, l] = history.back();
*ptr = old;
if (old != EMPTY)
old->l = l;
history.pop_back();
}
}
void solve() {
int n;
cin >> n;
adj.assign(n + 1, {});
for (int i = 1, u, v, w; i < n; ++i) {
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
for (int i = 2; i <= n; ++i)
cin >> s[i] >> v[i];
go(1, 0, 0);
for (int i = 2; i <= n; ++i)
cout << dp[i] << ' ';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef HALZOOM
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
#endif
int test = 1;
// cin >> test;
for (int i = 1; i <= test; ++i) {
solve();
}
return 0;
}
