//
// 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>
struct Line {
int m;
ll b;
ll f(ll x) { return 1LL * m * x + b; }
};
vector<int> values;
const ll inf = 4e18;
struct LiChao {
v<Line> seg;
struct Hist {
int idx;
int m;
ll b;
};
stack<Hist> st;
ll sz = 1;
LiChao(ll n1) {
for (; sz < n1; sz *= 2)
;
seg.resize(2 * sz, {0, inf});
}
void update(ll i, ll l, ll r, Line &add) {
ll mid = (l + r) / 2;
ll x_val = values[mid];
if (add.f(x_val) < seg[i].f(x_val)) {
st.push({(int)i, seg[i].m, seg[i].b});
swap(add, seg[i]);
}
if (l == r)
return;
ll x_l = values[l], x_r = values[r];
if (add.f(x_l) < seg[i].f(x_l)) {
update(i * 2, l, mid, add);
} else if (add.f(x_r) < seg[i].f(x_r))
update(i * 2 + 1, mid + 1, r, add);
else
return;
}
ll query(ll i, ll l, ll r, ll x) {
ll res = seg[i].f(x);
if (l == r)
return res;
ll 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));
}
};
v<ll> dp;
int n;
v<pll> kn;
v<v<pll>> g;
v<int> dpt;
int values_n;
void rollback(LiChao &lc, ll pic) {
while (lc.st.size() > pic) {
auto h = lc.st.top();
lc.seg[h.idx] = {h.m, h.b};
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 + sp * d + qu;
dp[node] = my_dp;
}
Line addi = {-d, dp[node]};
lc.update(1, 0, values_n - 1, addi);
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);
Line bb = {0, 0};
lc.update(1, 0, values_n - 1, bb);
dfs(0, -1, lc);
lp(i, 1, n) { cout << dp[i] << " "; }
return 0;
}
