#include <bits/stdc++.h> using namespace std; using ll = long long; template <class a, class b> ostream& operator<<(ostream &l, const pair<a, b> &r) { l << "(" << r.first << ", " << r.second << ")"; return l; } template <class t, unsigned long int s> ostream& operator<<(ostream &l, const array<t, s> &r) { l << "["; for (int i = 0; i + 1 < s; i++) l << r[i] << ", "; if (s > 0) l << r[s - 1]; l << "]"; return l; } template <class t> ostream& operator<<(ostream &l, const vector<t> &r) { l << "{"; for (int i = 0; i + 1 < r.size(); i++) l << r[i] << ", "; if (!r.empty()) l << r.back(); l << "}"; return l; } ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && (a % b)); } struct line { ll m, b, i; ll eval(ll x) { return m * x + b; } }; ll inter(const line &l, const line &r) { return fdiv(l.b - r.b, r.m - l.m); }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<vector<pair<int, int>>> adj(n); for (int i = 1; i < n; i++) { int a, b, c; cin >> a >> b >> c; a--, b--; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } vector<int> s(n), t(n); for (int i = 1; i < n; i++) { cin >> s[i] >> t[i]; } vector<ll> dp(n); deque<line> dq; dq.push_back({0, 0}); vector<line> mods; mods.reserve(n); auto qry = [&](ll x) -> ll { int l = 0, r = dq.size() - 1; while (l < r) { int m = (l + r) / 2; if (dq[m + 1].i >= x) { r = m; } else { l = m + 1; } } return dq[l].eval(x); }; auto upd = [&](ll m, ll b) -> int { int cp = mods.size(); line x = { m, b, -1 }; while (dq.size() > 1 && inter(x, dq.back()) <= dq.back().i) { mods.push_back(dq.back()); dq.pop_back(); } mods.push_back({LONG_LONG_MAX, LONG_LONG_MAX}); x.i = inter(x, dq.back()); dq.push_back(x); return cp; }; auto undo = [&](int x) -> void { while (mods.size() > x) { line l = mods.back(); mods.pop_back(); if (l.m == LONG_LONG_MAX) { dq.pop_back(); } else { dq.push_back(l); } } }; // dp[i] = s[i] + min_p(dp[p] + t[i] * (d[i] - d[p])) // = s[i] + min_p(dp[p] - t[i] * d[p]) + t[i] * d[i] // t[i] arbitrary -> queries arbitrary // d[p] increases -> slope decreases // negate both m and b -> flip across y axis -> query for min becomes max, lines inserted in increasing slope auto dfs = [&](int v, int p, ll d, auto &&self) -> void { int cp; if (p != -1) { dp[v] = -qry(t[v]) + s[v] + d * t[v]; cp = upd(d, -dp[v]); } for (pair<int, int> &i : adj[v]) { if (i.first != p) { self(i.first, v, d + i.second, self); } } if (p != -1) { undo(cp); } }; dfs(0, -1, 0, dfs); for (int i = 1; i < n - 1; i++) { cout << dp[i] << " "; } cout << dp[n - 1] << '\n'; }