#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INFLL = (1LL<<62);
// Line: y = m*x + b
struct Line {
ll m, b;
long double xLeft; // from which x this line becomes best
Line(ll _m=0, ll _b=INFLL, long double _x = -1e300L) : m(_m), b(_b), xLeft(_x) {}
// safe evaluation using __int128
ll eval(ll x) const {
__int128 v = (__int128)m * (__int128)x + (__int128)b;
if (v > (__int128)INFLL) return INFLL;
if (v < -(__int128)INFLL) return -INFLL;
return (ll)v;
}
};
// Monotonic CHT for minimum queries with strictly decreasing slopes
struct MonotonicCHT {
vector<Line> hull;
// compute x-coordinate of intersection of l1 and l2
static long double intersectX(const Line &l1, const Line &l2) {
// (b2 - b1) / (m1 - m2)
// m1 != m2 guaranteed
long double num = (long double)(l2.b - l1.b);
long double den = (long double)(l1.m - l2.m);
return num / den;
}
void clear() { hull.clear(); }
// Insert line with slope strictly decreasing
void add_line(ll m, ll b) {
Line nl(m,b,-1e300L);
if (hull.empty()) {
nl.xLeft = -1e300L;
hull.push_back(nl);
return;
}
// pop while new line makes last line irrelevant
while (!hull.empty()) {
long double x = intersectX(hull.back(), nl);
if (x <= hull.back().xLeft) {
hull.pop_back();
} else {
nl.xLeft = x;
break;
}
}
if (hull.empty()) nl.xLeft = -1e300L;
hull.push_back(nl);
}
// pop lines back to size sz
void rollback_to_size(int sz) {
if ((int)hull.size() > sz) hull.resize(sz);
}
// query min at x
ll query(ll x) const {
if (hull.empty()) return INFLL;
// find rightmost line with xLeft <= x
int l = 0, r = (int)hull.size() - 1, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (hull[mid].xLeft <= (long double)x) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
return hull[ans].eval(x);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if (!(cin >> N)) return 0;
vector<vector<pair<int,int>>> adj(N);
for (int i = 0; i < N-1; ++i) {
int u,v,d; cin >> u >> v >> d;
--u; --v;
adj[u].push_back({v,d});
adj[v].push_back({u,d});
}
vector<ll> S(N,0), V(N,0);
for (int i = 1; i < N; ++i) cin >> S[i] >> V[i];
// compute dist[] and parent[] using iterative BFS/DFS (root = 0)
vector<ll> dist(N,0);
vector<int> parent(N, -1), order;
order.reserve(N);
parent[0] = -2;
order.push_back(0);
for (size_t i = 0; i < order.size(); ++i) {
int u = order[i];
for (auto [v,w] : adj[u]) if (parent[v] == -1) {
parent[v] = u;
dist[v] = dist[u] + w;
order.push_back(v);
}
}
vector<ll> dp(N,0);
MonotonicCHT cht;
// iterative DFS stack of frames: (node, parent, next-child-index, state)
// state 0 = entry not processed, state 1 = exit (rollback)
struct Frame { int u, p; int it; bool entered; };
vector<Frame> stk;
stk.push_back({0, -1, 0, false});
while (!stk.empty()) {
Frame fr = stk.back(); stk.pop_back();
int u = fr.u, p = fr.p;
if (!fr.entered) {
// ENTRY
// compute dp
if (u == 0) dp[u] = 0;
else {
ll best = cht.query(V[u]);
// best should exist because root line is inserted before any children queries
dp[u] = best;
if (dp[u] >= INFLL/4) dp[u] = INFLL;
else dp[u] = dp[u] + dist[u] * V[u] + S[u];
}
// record hull size for rollback
int prevSize = (int)cht.hull.size();
// push EXIT frame with prevSize encoded in it field
stk.push_back({u, p, prevSize, true});
// insert this node's line: slope = -dist[u], intercept = dp[u]
cht.add_line(-dist[u], dp[u]);
// push children for entry
for (auto &ed : adj[u]) {
int v = ed.first;
if (v == p) continue;
stk.push_back({v, u, 0, false});
}
} else {
// EXIT: rollback hull to previous size stored in it
cht.rollback_to_size(fr.it);
}
}
// output dp[1..N-1]
for (int i = 1; i < N; ++i) {
cout << dp[i] << (i+1 < N ? ' ' : '\n');
}
return 0;
}
