#include <bits/stdc++.h> using namespace std; using ll = long long; using line = pair<ll, ll>; #define m first #define b second 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)); } 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); vector<line> dq(n); dq[0] = {0, 0}; int size = 1; auto qry = [&](ll x) -> ll { int l = 0, r = size - 1; while (l < r) { int mi = (l + r) / 2; if (inter(dq[mi], dq[mi + 1]) >= x) { r = mi; } else { l = mi + 1; } } return dq[l].m * x + dq[l].b; }; auto ins = [&](const line &x) -> int { // first spot where inter(x, dq[i + 1]) <= inter(dq[i], dq[i + 1]) int l = 0, r = size - 1; while (l < r) { int mi = (l + r) / 2; if (inter(x, dq[mi + 1]) <= inter(dq[mi], dq[mi + 1])) { r = mi; } else { l = mi + 1; } } return 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, sz; line x; if (p != -1) { dp[v] = -qry(t[v]) + s[v] + d * t[v]; // where the line would go x = {d, -dp[v]}; cp = ins(x) + 1; swap(dq[cp], x); sz = size; size = cp + 1; } for (pair<int, int> &i : adj[v]) { if (i.first != p) { self(i.first, v, d + i.second, self); } } if (p != -1) { size = sz; swap(dq[cp], x); } }; dfs(0, -1, 0, dfs); for (int i = 1; i < n - 1; i++) { cout << dp[i] << " "; } cout << dp[n - 1] << '\n'; }