#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;
struct Line {
LL a, b;
Line(LL a = 0, LL b = LLONG_MAX) : a(a), b(b) {}
inline LL F(LL x) const { return a * x + b; }
};
struct State {
int size;
int add_pos;
Line val;
};
template <bool IS_MAX = true>
struct CHT {
public:
// transform a user-provided line to the internal representation:
// if IS_MAX==true we store (-a,-b) so the structure (which finds minima)
// can be reused. Query results are negated back.
inline Line transform(Line L) const {
if constexpr (IS_MAX) return Line(-L.a, -L.b);
else return L;
}
long double get_intersec(const Line &x, const Line &y) const {
// caller must ensure x.a != y.a
return (long double)(y.b - x.b) / (x.a - y.a);
}
vector<Line> line; // storage for lines (internal/transformed)
vector<State> order; // rollback stack
int cur_size = 0;
CHT() = default;
// prepare internal arrays for up to n lines (n = number of adds expected)
void reload_size(int n) {
line.assign(n + 3, Line());
cur_size = 0;
order.clear();
}
// add a line (user gives normal line). Slopes must be strictly increasing.
void add_line(Line userL) {
Line x = transform(userL);
// binary search to find insertion position (keeps intersections monotone)
int low = 1, high = cur_size - 1;
int pos = cur_size;
// If cur_size==0 -> pos stays 0 -> we will set line[0] = x
while (low <= high) {
int mid = (low + high) >> 1;
// ensure we don't divide by zero inside get_intersec calls:
// mid-1 and mid are valid indices and should have different slopes
long double inter1 = get_intersec(line[mid - 1], line[mid]);
long double inter2 = get_intersec(line[mid], x);
if (inter1 >= inter2) {
pos = mid;
high = mid - 1;
} else low = mid + 1;
}
// save previous state for rollback
if ((int)order.size() == 0 || order.back().size != cur_size || order.back().add_pos != pos || !(order.back().val.a == line[pos].a && order.back().val.b == line[pos].b)) {
order.push_back({cur_size, pos, line[pos]});
} else {
// still push to preserve 1:1 with add operations (safer)
order.push_back({cur_size, pos, line[pos]});
}
cur_size = pos + 1;
line[pos] = x;
}
// query at x (user x). Works for arbitrary x (binary search on intersections).
// returns the actual requested value (min or max, depending on template)
LL Get(LL xval) const {
if (cur_size == 0) return LLONG_MAX; // no lines
int low = 1, high = cur_size - 1, pos = 0;
while (low <= high) {
int mid = (low + high) >> 1;
long double inter = get_intersec(line[mid - 1], line[mid]);
if (inter <= (long double)xval) {
pos = mid;
low = mid + 1;
} else high = mid - 1;
}
LL raw = line[pos].F(xval);
if constexpr (IS_MAX) return -raw; // negate back for max
else return raw; // already min
}
// rollback last add
void rollback() {
if (order.empty()) return;
State s = order.back();
order.pop_back();
cur_size = s.size;
line[s.add_pos] = s.val;
}
};
CHT<true> 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.Get(v[node]) + v[node] * d + c[node];
cht.add_line(Line(-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];
}
cht.reload_size(n);
dfs(0);
for(int i = 1 ; i < n ; i++) cout << dp[i] << " ";
cout<<'\n';
}
