#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ones(n) __builtin_popcountll(n)
#define msb(n) (63 - __builtin_clzll(n))
#define lsb(n) __builtin_ctzll(n)
constexpr int N = 2e5 + 5, M = 1e3 + 5, LOG = 31;
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3f;
constexpr int MOD = 1e9 + 7;
constexpr double eps = 1e-9, PI = acos(-1);
struct Line {
ll m, c;
Line() : m(0), c(llinf) {
}
Line(ll m, ll c) : m(m), c(c) {
}
ll eval(ll x) const { return m * x + c; }
};
struct RollbackCHT {
struct History {
int pos;
int sz;
Line old_line;
};
vector<Line> st;
vector<History> hist;
int sz;
RollbackCHT(int max_nodes = N) {
st.resize(max_nodes);
sz = 0;
}
// Checks if l2 is redundant given l1 and l3 (Lower Envelope)
bool redundant(Line l1, Line l2, Line l3) {
__int128 dx1 = l1.m - l2.m;
__int128 dc1 = l2.c - l1.c;
__int128 dx2 = l2.m - l3.m;
__int128 dc2 = l3.c - l2.c;
return dc1 * dx2 >= dc2 * dx1;
}
// Adds a line and internally records the state needed to undo it
void add(ll m, ll c) {
Line l_new(m, c);
int pos = sz;
int low = 1, high = sz - 1;
// Binary search insertion point
while (low <= high) {
int mid = low + (high - low) / 2;
if (redundant(st[mid - 1], st[mid], l_new)) {
pos = mid;
high = mid - 1;
}
else {
low = mid + 1;
}
}
// Push to internal history stack
hist.push_back({pos, sz, st[pos]});
// Apply change
st[pos] = l_new;
sz = pos + 1;
}
// Reverts the CHT to the state before the last add() call
void rollback() {
if (hist.empty()) return;
History h = hist.back();
hist.pop_back();
sz = h.sz;
st[h.pos] = h.old_line;
}
// Binary search to find the minimum value at x
ll query(ll x) {
if (sz == 0) return llinf;
int low = 0, high = sz - 2;
int best = sz - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (st[mid].eval(x) <= st[mid + 1].eval(x)) {
best = mid;
high = mid - 1; // Minimum is to the left or at mid
} else {
low = mid + 1; // Minimum is to the right
}
}
return st[best].eval(x);
}
};
int s[N], v[N];
ll dp[N];
vector<pair<int, int>> adj[N];
RollbackCHT cht;
void dfs(int u, int p, ll dist) {
if (u != 1) {
dp[u] = cht.query(v[u]);
dp[u] += dist * v[u] + s[u];
}
for (auto [nxt, w] : adj[u]) {
if (nxt != p) {
cht.add(-dist, dp[u]);
dfs(nxt, u, dist + w);
cht.rollback();
}
}
}
void testCase() {
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v_node, d;
cin >> u >> v_node >> d;
adj[u].eb(v_node, d);
adj[v_node].eb(u, d);
}
for (int i = 2; i <= n; i++)
cin >> s[i] >> v[i];
dp[1] = 0;
dfs(1, 1, 0);
for (int i = 2; i <= n; i++)
cout << dp[i] << (i == n ? "" : " ");
cout << '\n';
}
void preCompute() {
}
int32_t main() {
#ifdef C_Lion
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("errors.txt", "w", stderr);
#else
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cout << fixed << setprecision(static_cast<int32_t>(-log10(eps)));
preCompute();
int tc = 1;
// cin >> tc;
for (int TC = 1; TC <= tc; TC++) {
// cout << "Case #" << TC << ": ";
testCase();
}
}
/*
*/
