#include <bits/stdc++.h>
#include <cmath>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<class T> using ordered_set = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
void flash(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
void fileIO()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
#define all(a) a.begin(),a.end()
#define all_r(a) a.rbegin(),a.rend()
#define int long long
// REMEMBER IF YOU CHANGED ANYTHING
// FOCUS
// READ THE STATEMENT CAREFULLY
// no AI
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int mod = 1e9+7, N = 1e5 + 5, oo = 1e9;
template<bool IS_MAX = false, bool IS_INC = false>
struct RollbackCHT {
struct Line {
int m, c;
Line() : m(0), c(2e18) {} // Using a large value for inf
Line(int m, int c) : m(m), c(c) {}
int eval(int 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) {
// Use __int128 to prevent overflow during cross-multiplication
__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(int m, int c) {
int m_int = IS_INC ? -m : m;
int c_int = IS_MAX ? -c : c;
Line l_new(m_int, c_int);
int pos = sz;
int low = 1, high = sz - 1;
// Binary search for the insertion point to maintain the hull
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;
}
}
// Store history for the rollback operation
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;
}
int query(int x) {
if (sz == 0) return IS_MAX ? -2e18 : 2e18;
int x_int = (IS_INC != IS_MAX) ? -x : x;
int low = 0, high = sz - 2;
int best = sz - 1;
// Binary search for the optimal line
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;
}
}
int ans = st[best].eval(x_int);
return IS_MAX ? -ans : ans;
}
};
vector<int> a;
vector<int> b;
vector<int> dp;
vector<vector<pair<int, int>>> adj;
RollbackCHT<false, false> cht(N);
void dfs(int u, int p, int dis) {
if (p) {
dp[u] = a[u] + (dis * b[u]) + cht.query(b[u]);
}
cht.add(-dis, dp[u]);
for (auto& [v, w] : adj[u]) {
if (v == p) {
continue;
}
dfs(v, u, dis + w);
}
cht.rollback();
}
void solve() {
int n;
cin>>n;
a.assign(n+1, 0);
b.assign(n+1, 0);
dp.assign(n+1, 0);
adj.assign(n+1, {});
for (int i = 0; i < n-1; i++) {
int x, y, w;
cin>>x>>y>>w;
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
for (int i = 2; i <= n; i++) {
cin>>a[i]>>b[i];
}
dfs(1, 0, 0);
for (int i = 2; i <= n; i++) {
cout<<dp[i]<<' ';
}
}
signed main(void) {
flash();
fileIO();
// freopen("promote.in", "r", stdin);
// freopen("promote.out", "w", stdout);
int t = 1;
// cin>>t;
int tt = 1;
while(t--) {
//cout<<"Case #"<<tt++<<": ";
solve();
}
}
