#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;
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;
auto qry = [&](ll x) -> ll {
int l = 0, r = dq.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (inter(dq[m], dq[m + 1]) >= x) {
r = m;
} else {
l = m + 1;
}
}
return dq[l].eval(x);
};
auto upd = [&](const line& x) -> int {
int cp = mods.size();
while (dq.size() > 1 && inter(x, dq.back()) <= inter(dq.back(), dq[dq.size() - 2])) {
mods.push_back(dq.back());
dq.pop_back();
}
mods.push_back({LONG_LONG_MAX, LONG_LONG_MAX});
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';
}
