#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 = 1e5 + 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);
const ll maxN = 1e7 + 5;
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;
}
// Persistent Li Chao
constexpr int MAX_NODES = 4000005; // ~N * log(Domain) is roughly 10^5 * 31 = 3.1M
struct Node {
Line line;
int left, right;
} lct[MAX_NODES];
int node_cnt = 0;
int newNode(Line l = Line()) {
int u = ++node_cnt;
lct[u].line = l;
lct[u].left = lct[u].right = 0;
return u;
}
int copyNode(int u) {
int v = ++node_cnt;
lct[v] = lct[u];
return v;
}
int add(int u, Line toAdd, int l = -maxN + 1, int r = maxN - 1) {
int mid = l + (r - l) / 2;
int cur = u ? copyNode(u) : newNode(); // Copy if exists, else create blank
if (l == r) {
if (sub(l, toAdd) < sub(l, lct[cur].line))
swap(toAdd, lct[cur].line);
return cur;
}
bool lef = sub(l, toAdd) < sub(l, lct[cur].line);
bool midE = sub(mid + 1, toAdd) < sub(mid + 1, lct[cur].line);
if (midE) swap(lct[cur].line, toAdd);
if (lef != midE) {
lct[cur].left = add(lct[cur].left, toAdd, l, mid);
}
else {
if (mid + 1 <= r)
lct[cur].right = add(lct[cur].right, toAdd, mid + 1, r);
}
return cur;
}
ll query(int u, ll x, int l = -maxN + 1, int r = maxN - 1) {
if (!u) return llinf; // Null node
int mid = l + (r - l) / 2;
ll ans = sub(x, lct[u].line);
if (l == r) return ans;
if (x <= mid)
ans = min(ans, query(lct[u].left, x, l, mid));
else
ans = min(ans, query(lct[u].right, x, mid + 1, r));
return ans;
}
int root[N];
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) {
dp[u] = query(root[u], v[u]);
dp[u] += dist * v[u] + s[u];
}
for (auto [v, w] : adj[u]) {
if (v == p)
continue;
root[v] = add(root[u], {-dist, dp[u]});
dfs(v, u, dist + w);
}
}
void testCase() {
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v, d;
cin >> u >> v >> d;
adj[u].eb(v, d);
adj[v].eb(u, d);
}
for (int i = 2; i <= n; i++)
cin >> s[i] >> v[i];
add(root[1], {0, 0});
dfs(1, 1, 0);
for (int i = 2; i <= n; i++)
cout << dp[i] << ' ';
}
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("harbingers.in", "r", stdin);
// freopen("harbingers.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false), cin.tie(nullptr);
preCompute();
int tc = 1;
// cin >> tc;
for (int TC = 1; TC <= tc; TC++) {
// cout << "Case #" << TC << ": ";
testCase();
}
}
/*
*/
