#include <iostream>
#include <sstream>
#include <set>
#include <fstream>
#include <algorithm>
#include <cctype>
#include <iomanip>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <numeric>
#include <string>
#include <cmath>
#include <climits>
#include <stack>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <bitset>
#include <cassert>
#include <tuple>
#include <iterator>
#include <random>
#include <chrono>
#include <list>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1e5 + 5;
//const int mod=998244353;
const int mod=1e9+7;
// IS_MAX: Set to true for Maximum queries, false for Minimum queries.
// IS_INC: Set to true if slopes added are strictly Increasing, false for Decreasing.
template<bool IS_MAX = false, bool IS_INC = false>
struct RollbackCHT {
struct Line {
ll m, c;
Line() : m(0), c(1e18) {}
Line(ll m, ll c) : m(m), c(c) {}
ll eval(ll x) const { return m * x + c; }
};
struct History {
int pos;
int sz;
Line old_line;
};
vector<Line> st;
vector<History> hist;
int sz;
RollbackCHT(int max_nodes) {
st.resize(max_nodes);
sz = 0;
}
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;
}
void add(ll m, ll c) {
// The magic happens here: automatically formats internal state
ll m_int = IS_INC ? -m : m;
ll c_int = IS_MAX ? -c : c;
Line l_new(m_int, c_int);
int pos = sz;
int low = 1, high = sz - 1;
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;
}
}
hist.push_back({pos, sz, st[pos]});
st[pos] = l_new;
sz = pos + 1;
}
void rollback() {
if (hist.empty()) return;
History h = hist.back();
hist.pop_back();
sz = h.sz;
st[h.pos] = h.old_line;
}
ll query(ll x) {
if (sz == 0) return IS_MAX ? -1e18 : 1e18;
// The magic happens here: matches x to the internal geometry
ll x_int = (IS_INC != IS_MAX) ? -x : x;
int low = 0, high = sz - 2;
int best = sz - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (st[mid].eval(x_int) <= st[mid + 1].eval(x_int)) {
best = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
ll ans = st[best].eval(x_int);
return IS_MAX ? -ans : ans;
}
};
RollbackCHT<> cht(N);
int n;
vector <pair<int,int>> adj[N];
int s[N],val[N];
ll dp[N];
void dfs(int v,int p,ll d) {
if (v==1) dp[1]=0;
else dp[v]=s[v]+val[v]*d+cht.query(val[v]);
cht.add(-d,dp[v]);
for (auto u : adj[v]) {
if (u.first==p) continue;
dfs(u.first,v,d+u.second);
}
cht.rollback();
}
void solve() {
cin>>n;
for (int i=0;i<n-1;i++) {
int a,b,d;
cin>>a>>b>>d;
adj[a].push_back({b,d});
adj[b].push_back({a,d});
}
for (int i=2;i<=n;i++) {
cin>>s[i]>>val[i];
}
s[1]=val[1]=0;
dfs(1,0,0);
for (int i=2;i<=n;i++) cout<<dp[i]<<" ";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while (t--) {
solve();
}
return 0;
}
