#include <bits/stdc++.h>
using namespace std;
//long long MOD = 1e9 + 7;
const long long MOD = 998244353;
// const long long MOD = 100000007 ;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define popCnt(x) (__builtin_popcountll(x))
#define int long long
#define ld long double
#define F first
#define S second
#define pi M_PI
#define all(x) x.begin() , x.end()
#define ll long long
#define SZ(v) (int)(v.size())
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const long long OO = LLONG_MAX / 4, N = 3e5 + 5, M = 1e5 + 5, K = 505;
// rollback-capable LineContainer
struct Line {
mutable ll k, m, p;
bool operator<(const Line &o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct RollbackLineContainer : multiset<Line, less<>> {
static const ll inf = LLONG_MAX;
bool isMn = true;
// low-level op types for rollback logging
enum OpType { OP_INSERT, OP_ERASE, OP_SETP };
struct Op {
OpType type;
Line ln; // a copy of the affected line (stores old p for SETP)
};
// history of operations (each add produces a vector<Op>)
vector<vector<Op>> history;
// integer division floor for negatives like in original code
ll divll(ll a, ll b) {
return a / b - ((a ^ b) < 0 && a % b);
}
// helper: set p of an element (Line::p is mutable so can be changed even though element is "const")
void set_p(iterator it, ll newp) {
// mutate the mutable member
const_cast<ll&>(it->p) = newp;
}
// helper: find an element with exactly same (k,m). returns end() if not found.
iterator find_same(const Line &target) {
// use lower_bound(Line) which compares by k (operator<(Line))
auto it = lower_bound(target);
for (; it != end() && it->k == target.k; ++it) {
if (it->m == target.m) return it;
}
return end();
}
// erase with logging: log the erased copy then erase and return iterator to next element
iterator erase_with_log(iterator it, vector<Op> &ops) {
ops.push_back({OP_ERASE, *it}); // save copy before erasing
return erase(it);
}
// isect with logging: will record a SETP op (old copy) before changing x->p
// returns same boolean as original isect
bool isect_log(iterator x, iterator y, vector<Op> &ops) {
if (y == end()) {
if (x->p != inf) ops.push_back({OP_SETP, *x});
set_p(x, inf);
return false;
}
if (x->k == y->k) {
ll newp = (x->m > y->m ? inf : -inf);
if (x->p != newp) ops.push_back({OP_SETP, *x});
set_p(x, newp);
} else {
ll newp = divll(y->m - x->m, x->k - y->k);
if (x->p != newp) ops.push_back({OP_SETP, *x});
set_p(x, newp);
}
return x->p >= y->p;
}
// add as before but log all low-level changes into a vector<Op> and push it to history
void add(ll k, ll m) {
vector<Op> ops; ops.reserve(8); // small reservation to reduce reallocation
if (isMn) { k = -k; m = -m; }
// insert new line (p will be fixed by isect calls)
auto z = insert({k, m, 0});
ops.push_back({OP_INSERT, *z}); // remember insertion (copy)
auto y = z++;
auto x = y;
while (isect_log(y, z, ops)) z = erase_with_log(z, ops);
if (x != begin() && isect_log(--x, y, ops)) {
// if isect(--x,y) true then we must erase y and re-isect the new predecessor
y = erase_with_log(y, ops);
isect_log(x, y, ops);
}
while ((y = x) != begin()) {
--x;
if (x->p >= y->p) {
// erase y (log it) and re-evaluate intersection on x
auto nxt = erase_with_log(y, ops);
isect_log(x, nxt, ops);
} else break;
}
history.push_back(move(ops));
}
// query unchanged
ll query(ll x) {
auto l = *lower_bound(x);
return (isMn ? -1 : 1) * (l.k * x + l.m);
}
// rollback the last add (revert logged ops in reverse order)
void rollback() {
if (history.empty()) return;
auto ops = move(history.back());
history.pop_back();
// revert in reverse order
for (auto it = ops.rbegin(); it != ops.rend(); ++it) {
switch (it->type) {
case OP_ERASE:
// inverse of erase is insert the stored copy back
insert(it->ln);
break;
case OP_SETP: {
// inverse of set-p: find the element with same (k,m) and restore old p
auto found = find_same(it->ln);
if (found != end()) set_p(found, it->ln.p);
break;
}
case OP_INSERT: {
// inverse of insert is remove the inserted line (find by k,m)
auto found = find_same(it->ln);
if (found != end()) erase(found);
break;
}
}
}
}
// rollback last t adds (if t > history.size() we rollback everything)
void rollback_n(size_t t) {
while (t-- && !history.empty()) rollback();
}
// clear history (forget ability to rollback)
void clear_history() {
history.clear();
}
};
RollbackLineContainer cht;
int n;
vector<int> v, c;
vector<vector<pair<int, int>>> adj;
vector<int> dp;
void dfs(int node , int p = -1 , int d = 0)
{
if(p == -1) dp[node] = 0;
else dp[node] = cht.query(v[node]) + v[node] * d + c[node];
cht.add(-d , dp[node]);
for(auto [child , len] : adj[node])
{
if(child == p)continue;
dfs(child , node , d + len);
}
cht.rollback();
}
signed main() {
fast;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n;
dp = v = c = vector<int>(n);
adj.resize(n);
for (int i = 0; i < n - 1; ++i) {
int u, vv, d;
cin >> u >> vv >> d;
u--;
vv--;
adj[u].emplace_back(vv, d);
adj[vv].emplace_back(u, d);
}
for (int i = 1; i < n; ++i) {
cin >> c[i] >> v[i];
}
dfs(0);
for(int i = 1 ; i < n ; i++) cout << dp[i] << " ";
cout<<'\n';
}
