#include <bits/stdc++.h>
using namespace std;
#define MOD1 1000000007
#define MOD2 998244353
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define lbound(v, x) lower_bound(all(v), x) - v.begin()
#define ubound(v, x) upper_bound(all(v), x) - v.begin()
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define FOR1(a) for (int _ = 0; _ < (a); ++_)
#define FOR2(i, a) for (int i = 0; i < (a); ++i)
#define FOR3(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR1(a) for (int _ = (a)-1; _ >= 0; --_)
#define RFOR2(i, a) for (int i = (a)-1; i >= 0; --i)
#define RFOR3(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define overload3(a, b, c, d, ...) d
#define REP(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define RREP(...) overload3(__VA_ARGS__, RFOR3, RFOR2, RFOR1)(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef long double ld;
const ll INF = 1e15;
const ld eps = 1e-12;
struct Line {
ll m, b;
ld xLeft;
ll eval(ll x) const { return m * x + b; }
};
vector<Line> hull;
/*
* Each addLine may remove several lines.
* We record what was removed to allow undo().
*/
stack<vector<Line>> history;
ld intersectX(const Line &l1, const Line &l2) {
return (ld)(l1.b - l2.b) / (ld)(l2.m - l1.m);
}
/**
* Adds a new line to the convex hull.
* Maintains upper/lower hull monotonicity and
* records removed lines for O(1) rollback.
*/
void addLine(ll m, ll b) {
Line newL{m, b, 0};
vector<Line> popped;
// Remove all lines that are no longer needed
while (!hull.empty()) {
Line &l = hull.back();
if (l.m == newL.m) {
if (l.b <= newL.b) {
// This line is worse everywhere; no addition needed.
history.push({});
return;
}
popped.push_back(l);
hull.pop_back();
} else {
ld x = intersectX(l, newL);
if (x <= l.xLeft + eps) {
popped.push_back(l);
hull.pop_back();
} else break;
}
}
// Compute the xLeft intersection with the previous line
newL.xLeft = hull.empty() ? -1e30L : intersectX(hull.back(), newL);
hull.push_back(newL);
// Record what lines were popped for rollback
history.push(popped);
}
/**
* Undo the last line addition.
* Restores the hull exactly to its previous state.
*/
void undo() {
if (history.empty()) return;
vector<Line> &popped = history.top();
// Remove the line we added
if (!hull.empty()) hull.pop_back();
// Restore any previously popped lines
for (int i = (int)popped.size() - 1; i >= 0; --i)
hull.push_back(popped[i]);
history.pop();
}
/**
* Query the minimum y value at x.
* Hull must be sorted by xLeft.
*/
ll query(ll x) {
if (hull.empty()) return INF;
int low = 0, high = (int)hull.size() - 1;
while (low < high) {
int mid = (low + high + 1) / 2;
if (hull[mid].xLeft - eps <= (ld)x)
low = mid;
else
high = mid - 1;
}
return hull[low].eval(x);
}
vvpll adj;
vll ans;
vpll har;
/**
* Tree DP with rollback convex hull trick.
*/
void dfs(int u, int p = -1, ll d = 0) {
if (u == 0) {
// Root: initialize hull with y = 0
addLine(0, 0);
} else {
auto [s, t] = har[u];
ans[u] = query(t) + s + t * d;
addLine(-d, ans[u]);
}
for (auto [v, w] : adj[u]) {
if (v == p) continue;
dfs(v, u, d + w);
}
// Roll back to previous hull state
undo();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
adj.assign(n, {});
REP(i, n - 1) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
adj[u].pushb(mp(v, w));
adj[v].pushb(mp(u, w));
}
har.assign(n, {});
ans.assign(n, 0);
REP(i, 1, n) cin >> har[i].fir >> har[i].sec;
dfs(0);
REP(i, 1, n) cout << ans[i] << ' ';
cout << '\n';
}
