#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
// #define int long long
#define endl "\n"
//-------------------\\
const ll INF = 2e18;
const ll MIN_X = 1, MAX_X = 1e9;
struct Line {
ll m, b;
Line(ll _m = 0, ll _b = INF) : m(_m), b(_b) {
}
ll get(ll x) const { return m * x + b; }
};
struct Node {
Line line;
Node *left, *right;
Node(Line _line = Line()) : line(_line), left(nullptr), right(nullptr) {
}
// Copy Constructor for persistence
Node(Node *oldNode) {
if (oldNode) {
line = oldNode->line;
left = oldNode->left;
right = oldNode->right;
}
}
// Returns a pointer to the newly created root
Node *add(Line nw, ll l = MIN_X, ll r = MAX_X) {
Node *cur = new Node(this); // Do not modify the original
ll mid = l + (r - l) / 2;
bool lef = nw.get(l) < cur->line.get(l);
bool midf = nw.get(mid) < cur->line.get(mid);
if (midf) swap(cur->line, nw);
if (l == r) return cur;
if (lef != midf) {
if (!cur->left) cur->left = new Node();
cur->left = cur->left->add(nw, l, mid);
} else {
if (!cur->right) cur->right = new Node();
cur->right = cur->right->add(nw, mid + 1, r);
}
return cur;
}
ll query(ll x, ll l = MIN_X, ll r = MAX_X) const {
ll res = line.get(x);
if (l == r) return res;
ll mid = l + (r - l) / 2;
if (x <= mid && left) return min(res, left->query(x, l, mid));
if (x > mid && right) return min(res, right->query(x, mid + 1, r));
return res;
}
};
/*
Usage:
Node* root = new Node(); // Empty tree version 0
Node* new_root = root->add({m, c}); // Version 1 (Root unchanged)
ll ans = new_root->query(x);
*/
void solve() {
int n; cin >> n;
vector<vector<array<int,2>>> adj(n+1);
for (int i = 1;i < n; i++) {
int u,v,d; cin >> u >> v >> d;
adj[u].push_back({v,d});
adj[v].push_back({u,d});
}
int wait[n+1] = {}, speed[n+1] = {};
for (int i = 2; i <= n; i++) cin >> wait[i] >> speed[i];
ll ans[n+1] = {};
Node* root = new Node();
function<void(int,int,int,Node*)> go = [&](int u, int p, int d, Node* cur) {
if (u != 1) ans[u] = cur->query( speed[u]) + d * speed[u] + wait[u];
Node* nxt = cur->add({-d, ans[u]});
for (auto [v,dist] : adj[u]) {
if (v == p) continue;
go(v, u, d + dist, nxt);
}
}; go(1,0,0,root);
for (int i = 2;i <= n; i++) cout << ans[i] << " ";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(9);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
