#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NINF = LLONG_MIN / 4;
struct Line {
ll a, b;
Line(ll _a = 0, ll _b = NINF) : a(_a), b(_b) {}
};
struct Node {
int l = -1, r = -1; // children indices in pool
ll a = 0, b = NINF; // line: a * x + b
Node() = default;
Node(ll _a, ll _b) : l(-1), r(-1), a(_a), b(_b) {}
};
struct Change {
// either pointer-change (isPtr=true) -> *where should be restored to oldPtr
// or line-change (isPtr=false) -> pool[nodeIdx].(a,b) should be restored to oldLine
bool isPtr;
int *where; // address of int (root or pool[idx].l or pool[idx].r)
int oldPtr;
int nodeIdx;
Line oldLine;
Change(int* _where, int _oldPtr) : isPtr(true), where(_where), oldPtr(_oldPtr), nodeIdx(-1), oldLine() {}
Change(int _nodeIdx, Line _oldLine) : isPtr(false), where(nullptr), oldPtr(-1), nodeIdx(_nodeIdx), oldLine(_oldLine) {}
};
vector<Change> changes;
vector<Node> pool; // node pool
vector<ll> xs; // compressed x values (unique speeds)
inline size_t snapshot() { return changes.size(); }
inline void rollback(size_t snap, size_t pool_size_snap) {
// restore line changes and pointer changes
while (changes.size() > snap) {
Change c = changes.back();
changes.pop_back();
if (c.isPtr) {
*c.where = c.oldPtr;
} else {
pool[c.nodeIdx].a = c.oldLine.a;
pool[c.nodeIdx].b = c.oldLine.b;
}
}
// shrink pool back (discard nodes created after snapshot)
while (pool.size() > pool_size_snap) pool.pop_back();
}
int newNode(Line ln) {
pool.emplace_back(ln.a, ln.b);
return int(pool.size()) - 1;
}
inline ll evalLine(const Line &ln, ll x) {
return ln.a * x + ln.b;
}
inline ll evalNode(int idx, ll x) {
return pool[idx].a * x + pool[idx].b;
}
// insert into Li-Chao over indices [L,R] (indexes into xs)
void insert_line(int &cur, Line line, int L, int R) {
if (cur == -1) {
// record the pointer change (cur was -1)
changes.emplace_back(&cur, cur);
cur = newNode(line);
return;
}
if (pool[cur].a == line.a) {
// only possibly update b (we maintain max)
changes.emplace_back(cur, Line(pool[cur].a, pool[cur].b));
pool[cur].b = max(pool[cur].b, line.b);
return;
}
int mid = (L + R) >> 1;
ll xmid = xs[mid];
ll curMid = evalNode(cur, xmid);
ll newMid = evalLine(line, xmid);
if (newMid > curMid) {
changes.emplace_back(cur, Line(pool[cur].a, pool[cur].b));
// swap lines: keep best in node
swap(pool[cur].a, line.a);
swap(pool[cur].b, line.b);
}
if (L == R) return;
ll xl = xs[L], xr = xs[R];
ll curL = evalNode(cur, xl);
ll newL = evalLine(line, xl);
if (newL > curL) {
insert_line(pool[cur].l, line, L, mid);
return;
}
ll curR = evalNode(cur, xr);
ll newR = evalLine(line, xr);
if (newR > curR) {
insert_line(pool[cur].r, line, mid + 1, R);
}
}
ll query_idx(int idxX, int cur, int L, int R) {
if (cur == -1) return NINF;
ll res = evalNode(cur, xs[idxX]);
if (L == R) return res;
int mid = (L + R) >> 1;
if (idxX <= mid) {
return max(res, query_idx(idxX, pool[cur].l, L, mid));
} else {
return max(res, query_idx(idxX, pool[cur].r, mid + 1, R));
}
}
// ---------------- main solution ----------------
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, w; cin >> u >> v >> w; --u; --v;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<ll> S(n, 0), V(n, 0);
for (int i = 1; i < n; ++i) {
cin >> S[i] >> V[i];
}
// prepare compressed xs from speeds V[1..n-1]
xs.clear();
xs.reserve(n);
for (int i = 1; i < n; ++i) xs.push_back(V[i]);
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
if (xs.size() == 0) {
// degenerate (shouldn't happen since n>=3), but guard
xs.push_back(1);
} else if (xs.size() == 1) {
// avoid single-point domain; add one sentinel
xs.push_back(xs[0] + 1);
}
int m = int(xs.size());
// reserve pool to avoid relocation (keeps addresses stable)
pool.clear();
pool.reserve(4 * m + 5); // heuristic, reduces reallocations
changes.clear();
int root = -1;
vector<ll> dp(n, 0);
// DFS with rollback
// compute dist (distance from root) along recursion
function<void(int,int,ll)> dfs = [&](int u, int p, ll dist) {
size_t snap = snapshot();
size_t pool_snap = pool.size();
if (u == 0) {
dp[u] = 0;
} else {
// find index of V[u] in xs
int idx = int(lower_bound(xs.begin(), xs.end(), V[u]) - xs.begin());
ll best = query_idx(idx, root, 0, m - 1); // returns max(dist_x * V[u] - dp_x)
dp[u] = S[u] + V[u] * dist - best;
}
// insert this node's line for descendants: line = { dist, -dp[u] }
insert_line(root, Line(dist, -dp[u]), 0, m - 1);
for (auto &e : adj[u]) {
int v = e.first; int w = e.second;
if (v == p) continue;
dfs(v, u, dist + w);
}
rollback(snap, pool_snap);
};
dfs(0, -1, 0);
for (int i = 1; i < n; ++i) {
cout << dp[i] << (i + 1 < n ? ' ' : '\n');
}
return 0;
}
