#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
constexpr int N = 1e5 + 5;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3f;
struct Line {
ll m, c;
Line() : m(0), c(llinf) {}
Line(ll m, ll c) : m(m), c(c) {}
};
ll sub(ll x, Line l) {
return x * l.m + l.c;
}
// Safely checks if l2 is redundant given l1 and l3
// Uses __int128 to prevent overflow since (c2-c1) * (m2-m3) can reach 10^27
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;
}
Line st[N]; // Global CHT Stack
int sz = 0;
int s[N], v[N];
ll dp[N];
vector<pair<int, int>> adj[N];
void dfs(int u, int p, ll dist) {
if (u != 1) {
// Query minimum. Since values form a convex lower envelope,
// we can simply binary search the minimum by comparing adjacent values.
int low = 0, high = sz - 2;
int best = sz - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (sub(v[u], st[mid]) <= sub(v[u], st[mid + 1])) {
best = mid;
high = mid - 1; // Minimum is to the left or at mid
} else {
low = mid + 1; // Minimum is to the right
}
}
dp[u] = sub(v[u], st[best]) + dist * v[u] + s[u];
}
Line l_new(-dist, dp[u]);
int pos = sz;
int low = 1, high = sz - 1;
// Binary search to find where to insert the new line
while (low <= high) {
int mid = low + (high - low) / 2;
if (redundant(st[mid - 1], st[mid], l_new)) {
pos = mid;
high = mid - 1; // l_new overtakes earlier, move left
} else {
low = mid + 1; // st[mid] is strictly useful, move right
}
}
// --- ROLLBACK STATE SAVING ---
int old_sz = sz;
Line old_line = st[pos];
// Apply the new line
st[pos] = l_new;
sz = pos + 1;
for (auto [nxt, w] : adj[u]) {
if (nxt != p) {
dfs(nxt, u, dist + w);
}
}
// --- ROLLBACK RESTORE ---
sz = old_sz;
st[pos] = old_line;
}
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';
}
int32_t main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
testCase();
return 0;
}
