#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; } double inter(Line other) { return (double)(other.b - b) / (m - other.m); } }; struct CHT { v<Line> dq; struct History { int idx, sz; Line old; }; History insert(Line add) { int l = 1, r = dq.size() - 1; int pos = dq.size(); while (l <= r) { int mid = l + (r - l) / 2; if (dq[mid - 1].inter(dq[mid]) >= dq[mid - 1].inter(add)) { pos = mid; r = mid - 1; } else { l = mid + 1; } } History h = {pos, (int)dq.size(), {0, 0}}; if (pos < dq.size()) h.old = dq[pos]; if (pos < dq.size()) dq[pos] = add; else dq.push_back(add); dq.resize(pos + 1); return h; } void rollback(History h) { dq.resize(h.sz); if (h.idx < h.sz) dq[h.idx] = h.old; } ll query(ll x) { if (dq.empty()) return 0; int l = 0, r = dq.size() - 2; int idx = dq.size() - 1; while (l <= r) { int mid = l + (r - l) / 2; if (dq[mid].inter(dq[mid + 1]) >= x) { idx = mid; r = mid - 1; } else { l = mid + 1; } } return dq[idx].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] << " "; } }