#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define pushb push_back
#define mp make_pair
#define FOR2(i, a) for (int i = 0; i < (a); ++i)
#define FOR3(i, a, b) for (int i = (a); i < (b); ++i)
#define overload3(a, b, c, d, ...) d
#define REP(...) overload3(__VA_ARGS__, FOR3, FOR2)(__VA_ARGS__)
using ll = long long;
using ld = long double;
using pll = pair<ll,ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vll = vector<ll>;
static const ll INF = (ll)4e18;
static const int MAXN = 200000 + 5; // adjust if needed (must be >= n)
struct Line {
ll m, b;
Line(ll m=0, ll b=0): m(m), b(b) {}
ll eval(ll x) const {
// avoid overflow if needed:
__int128 v = (__int128)m * x + b;
if (v > (__int128)LLONG_MAX) return LLONG_MAX;
if (v < (__int128)LLONG_MIN) return LLONG_MIN;
return (ll)v;
}
};
// intersection x-coordinate of l1 and l2 (they must have different slopes)
static inline ld intersectX(const Line &l1, const Line &l2) {
// l1.m != l2.m
return (ld)(l2.b - l1.b) / (ld)(l1.m - l2.m);
}
// ---- CHT storage: fixed array like sample ----
static Line stk[MAXN];
static int stk_max = 0;
// query min at x (binary search on intersections)
static inline ll line_min(ll x) {
int l = 0, r = stk_max - 1;
while (l < r) {
int m = (l + r) >> 1;
if (intersectX(stk[m], stk[m + 1]) < (ld)x) l = m + 1;
else r = m;
}
return stk[l].eval(x);
}
// find position where new line should be placed, and hull after that is removed
static inline int remove_pos(const Line &line) {
if (stk_max < 2) return stk_max;
// if line belongs at the end (no removals)
if (intersectX(line, stk[stk_max - 1]) >= intersectX(stk[stk_max - 1], stk[stk_max - 2]))
return stk_max;
// binary search for first position to replace
int l = 1, r = stk_max - 1;
while (l < r) {
int m = (l + r) >> 1;
if (intersectX(line, stk[m]) < intersectX(stk[m], stk[m - 1])) r = m;
else l = m + 1;
}
return l;
}
// ---- Tree DP ----
vvpll adj;
vll ans;
vpll har;
void dfs(int u, int p = -1, ll d = 0) {
int prev_max = stk_max;
int prev_pos = -1;
Line prev_line;
if (u == 0) {
ans[u] = 0;
stk[stk_max++] = Line(0, 0);
} else {
auto [s, t] = har[u];
ll best = line_min(t);
__int128 val = (__int128)best + s + (__int128)t * d;
ans[u] = (ll)val;
Line nl(-d, ans[u]);
prev_pos = remove_pos(nl);
// we will overwrite stk[prev_pos] (if prev_pos < stk_max)
if (prev_pos < stk_max) prev_line = stk[prev_pos];
stk_max = prev_pos;
stk[stk_max++] = nl;
}
for (auto [v, w] : adj[u]) {
if (v == p) continue;
dfs(v, u, d + w);
}
// rollback
stk_max = prev_max;
if (prev_pos != -1 && prev_pos < prev_max) stk[prev_pos] = prev_line;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// safety: ensure MAXN is enough
if (n + 5 > MAXN) {
// In contests you'd just set MAXN big enough; this is just a guard.
// If this triggers, increase MAXN above.
return 0;
}
adj.assign(n, {});
REP(i, n - 1) {
int u, v;
ll w;
cin >> u >> v >> w;
--u; --v;
adj[u].pushb({v, w});
adj[v].pushb({u, w});
}
har.assign(n, {0, 0});
ans.assign(n, 0);
REP(i, 1, n) cin >> har[i].fir >> har[i].sec;
stk_max = 0;
dfs(0);
REP(i, 1, n) cout << ans[i] << ' ';
cout << '\n';
return 0;
}
