/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/CEOI09_harbingers
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 100007
#define MAXE 100007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
bool debug;
int N;
vii adjlist[MAXV];
ll delay[MAXV], speed[MAXV], d[MAXV];
ll dp[MAXV];
void dfs0(int v, int pv, ll depth) {
d[v] = depth;
for(auto x : adjlist[v]) {
if(x.fst == pv) continue;
dfs0(x.fst, v, depth + (ll)x.snd);
}
}
int q[MAXV], qct;
double crossPoint(int v1, int v2) {
return ((double)dp[v2] - (double)dp[v1]) / ((double)d[v2] - (double)d[v1]);
}
int bs(int v) {
int lo = 0, hi = qct-1, mid = 0;
while(lo < hi) {
mid = (lo+hi)/2;
if(debug) cout << "bs " << q[mid] << endl;
if(mid == qct-1 || mid == 0) {
lo = hi+1;
} else if(crossPoint(q[mid-1], q[mid]) > speed[v]) {
if(debug) cout << " .. hi goes down " << lo << " " << hi << endl;
hi = mid -1;
} else if(crossPoint(q[mid], q[mid+1]) < speed[v]) {
if(debug) cout << " .. lo goes up " << lo << " " << hi << endl;
lo = mid + 1;
} else {
if(debug) cout << " .. found " << q[mid] << endl;
lo = hi+1;
}
}
/// double confirm
while(mid-1>=0 && crossPoint(q[mid-1], q[mid]) > speed[v]) mid--;
while(mid+1<=qct-1 && crossPoint(q[mid], q[mid+1]) < speed[v]) mid++;
return q[mid];
}
void dfs(int v, int pv) {
if(debug) {
cout << "work on " << v << endl;
for(int i=0; i< qct; i++) cout << q[i] << " ";
cout << endl;
}
dp[v] = delay[v] + speed[v] * d[v];
if(qct>0) {
int j;
if(qct==1) {
j = q[0];
} else if(qct==2) {
j = q[0];
if(crossPoint(q[0], q[1]) < speed[v]) j = q[1];
} else {
if(debug) cout << " .. go bs" << endl;
j = bs(v);
if(debug) cout << " .. bs find " << j;
}
ll ndp = dp[v] + dp[j] - d[j] * speed[v];
dp[v] = min(dp[v], ndp);
}
if(debug) cout << v << " " << dp[v] << endl;
vi store;
store.clear();
while(qct>=2 && crossPoint(qct-2, qct-1) > crossPoint(qct-1, v)) {
store.pb(q[qct-1]);
qct--;
}
q[qct] = v; qct++;
for(auto x : adjlist[v]) {
if(x.fst == pv) continue;
dfs(x.fst, v);
}
qct--;
for(int i = sz(store)-1; i>=0; i--) {
q[qct] = store[i]; qct++;
}
store.clear();
}
int main() {
debug = false;
ios_base::sync_with_stdio(false); cin.tie(0);
int i, j, k;
int ans = 0;
cin >> N ;
for(i=1;i<=N-1;i++) {
int a, b, c; cin >> a >> b >> c;
adjlist[a].pb(mp(b,c)); adjlist[b].pb(mp(a,c));
}
for(i=2;i<=N;i++) cin >> delay[i] >> speed[i];
dfs0(1,0,0LL);
if(debug) cout << "complete setup" << endl;
qct = 0;
dfs(1, 0);
if(debug) cout << "complete calculation" << endl;
for(i =2; i<=N; i++) cout << dp[i] << " ";
}
