// // Created by liasa on 13/12/2025. // #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) #define pll pair<ll, ll> vector<int> values; const ll inf = 4e18; v<ll> dp; int n; v<pll> kn; v<v<pll>> g; v<int> dpt; ll wh_line(int id, ll x) { if (id == -1) return inf; return dp[id] - 1LL * dpt[id] * x; } struct LiChao { v<int> seg; struct Hist { int idx, old_id; }; stack<Hist> st; int sz = 1; LiChao(int n1) { for (; sz < n1; sz *= 2) ; seg.resize(2 * sz, -1); } void update(int i, int l, int r, int add_id) { int mid = (l + r) / 2; ll x_val = values[mid]; int cur_id = seg[i]; if (wh_line(add_id, x_val) < wh_line(cur_id, x_val)) { st.push({i, cur_id}); seg[i] = add_id; add_id = cur_id; } if (l == r) return; ll x_l = values[l], x_r = values[r]; if (wh_line(add_id, x_l) < wh_line(seg[i], x_l)) { update(i * 2, l, mid, add_id); } else update(i * 2 + 1, mid + 1, r, add_id); } ll query(int i, int l, int r, ll x) { ll res = wh_line(seg[i], x); if (l == r) return res; int mid = (l + r) / 2; ll mid_val = values[mid]; if (x <= mid_val) { return min(res, query(i * 2, l, mid, x)); } else return min(res, query(i * 2 + 1, mid + 1, r, x)); } }; int values_n; void rollback(LiChao &lc, ll pic) { while (lc.st.size() > pic) { auto h = lc.st.top(); lc.seg[h.idx] = h.old_id; lc.st.pop(); } } // dp[v] = st[v] + sp[v]*dpt[v] + min(dp[u] - sp[v]*dpt[u] void dfs(int node, int par, LiChao &lc) { ll pic = lc.st.size(); int d = dpt[node]; if (node == 0) { dp[node] = 0; } else { auto [st, sp] = kn[node]; ll qu = lc.query(1, 0, values_n - 1, sp); ll my_dp = st + 1LL * sp * d + qu; dp[node] = my_dp; } lc.update(1, 0, values_n - 1, node); for (auto [it, d_add] : g[node]) { if (it != par) { dfs(it, node, lc); } } rollback(lc, pic); } void dfs1(ll node, ll par, ll dpa) { // values.push_back(dpa); dpt[node] = dpa; for (auto [it, d_add] : g[node]) { if (it != par) dfs1(it, node, dpa + d_add); } } 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, 0); lp(i, 0, n - 1) { ll a, b, c; cin >> a >> b >> c; a--; b--; g[a].push_back({b, c}); g[b].push_back({a, c}); } dp[0] = 0; dfs1(0, -1, 0); lp(i, 1, n) { ll st, speed; cin >> st >> speed; values.push_back(speed); kn[i] = {st, speed}; } sort(values.begin(), values.end()); values.erase(unique(values.begin(), values.end()), values.end()); values_n = values.size(); LiChao lc(values_n); lc.update(1, 0, values_n - 1, 0); dfs(0, -1, lc); lp(i, 1, n) { cout << dp[i] << " "; } return 0; }