#include <bits/stdc++.h> using namespace std; #define ll long long #define v vector #define lp(i, s, e) for (int i = s; i < e; ++i) struct Line { ll m, b; ll f(ll x) { return m * x + b; } }; struct CHT { v<Line> dq; struct History { int idx, sz; Line old; v<Line> removed; bool changed; bool replaced; }; bool bad(Line l1, Line l2, Line l3) { __int128 left = (__int128)(l3.b - l1.b) * (__int128)(l1.m - l2.m); __int128 right = (__int128)(l2.b - l1.b) * (__int128)(l1.m - l3.m); return left <= right; } History insert(Line add) { History h; h.idx = 0; h.sz = dq.size(); h.old = {0, 0}; h.removed.clear(); h.changed = false; h.replaced = false; if (!dq.empty() && dq.back().m == add.m) { if (dq.back().b <= add.b) return h; h.old = dq.back(); dq.pop_back(); h.removed.push_back(h.old); h.changed = true; h.replaced = true; } while (dq.size() >= 2 && bad(dq[dq.size() - 2], dq[dq.size() - 1], add)) { h.removed.push_back(dq.back()); dq.pop_back(); h.changed = true; } dq.push_back(add); h.changed = true; return h; } void rollback(History h) { if (!h.changed) return; dq.pop_back(); for (int i = h.removed.size() - 1; i >= 0; --i) dq.push_back(h.removed[i]); } ll query(ll x) { if (dq.empty()) return 0; int l = 0, r = dq.size() - 1; while (l < r) { int mid = (l + r) / 2; if (dq[mid].f(x) >= dq[mid + 1].f(x)) l = mid + 1; else r = mid; } return dq[l].f(x); } }; v<ll> dp, dpt; ll n; #define pll pair<ll, ll> v<pll> kn; v<v<pll>> g; void dfs(int node, int par, CHT &cht) { auto h = cht.insert({-dpt[node], dp[node]}); for (auto [it, c] : g[node]) { if (it == par) continue; dpt[it] = dpt[node] + c; dp[it] = kn[it].first + kn[it].second * dpt[it] + cht.query(kn[it].second); dfs(it, node, cht); } cht.rollback(h); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; g.resize(n); dp.resize(n); kn.resize(n); dpt.resize(n); lp(i, 1, n) { int a, b; ll w; cin >> a >> b >> w; a--; b--; g[a].push_back({b, w}); g[b].push_back({a, w}); } lp(i, 1, n) { cin >> kn[i].first >> kn[i].second; } CHT cht; dpt[0] = 0; dp[0] = 0; dfs(0, -1, cht); lp(i, 1, n) { cout << dp[i] << " "; } }