// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
// #pragma comment(linker, "/STACK:2000000")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define ui unsigned int
#define endl "\n"
#define FOCUS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void Go() {
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
// LLONG_MAX -> min f(x) , -LLONG_MAX -> max f(x)
// this min lichao
const ll DEFAULT = LLONG_MAX;
const ll INF = 1e18;
const int N = 2e9;
struct Line {
ll m, c;
Line(ll m = 0, ll c = DEFAULT) : m(m), c(c) {
}
ll operator()(ll x) const { return m * x + c; }
};
// this min lichao
struct Node {
Node *left, *right;
Line line;
Node(Line line = Line(), Node *left = nullptr, Node *right = nullptr)
: line(line), left(left), right(right) {
}
};
// this min lichao
Node *insert(Line newLine, Node *root, ll l = -N, ll r = N) {
if (root == nullptr) {
return new Node(newLine, nullptr, nullptr);
}
Node *cur = new Node(root->line, root->left, root->right);
ll m = l + (r - l) / 2;
// (<) -> min f(x) , (>) -> max f(x)
bool lef = newLine(l) < cur->line(l);
bool mid = newLine(m) < cur->line(m);
if (mid)
swap(cur->line, newLine);
if (r - l == 1)
return cur;
if (lef != mid)
cur->left = insert(newLine, cur->left, l, m);
else
cur->right = insert(newLine, cur->right, m, r);
return cur;
}
ll query(ll x, Node *cur, ll l = -N, ll r = N) {
if (cur == nullptr)
return DEFAULT;
ll m = l + (r - l) / 2;
if (r - l == 1)
return cur->line(x);
// min -> min f(x) , max -> max f(x)
else if (x < m)
return min(cur->line(x), query(x, cur->left, l, m));
else
return min(cur->line(x), query(x, cur->right, m, r));
}
vector<Node *> roots;
vector<vector<pair<int,int> > > adj;
vector<int> wait, speed;
vector<int> dp;
int n;
void solve(int node,int parent = -1,int dis = 0) {
int &ret = dp[node];
if (node) {
int x = speed[node];
ret = wait[node] + speed[node] * dis+ query(x, roots[parent]);
}
int m = -dis;
int b = dp[node];
Line temp = {m, b};
Node *parentP = ((parent == -1) ? nullptr : roots[parent]);
Node *cur = insert(temp, parentP);
roots[node] = cur;
for (auto [child,c]: adj[node]) {
if (child == parent)continue;
solve(child, node, dis + c);
}
}
signed main() {
FOCUS
// Go();
cin >> n;
dp = vector<int>(n);
adj = vector<vector<pair<int,int> > >(n);
roots = vector<Node *>(n);
roots[0] = nullptr;
for (int i = 0; i < n - 1; i++) {
int x, y, w;
cin >> x >> y >> w;
x--, y--;
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
wait = vector<int>(n);
speed = vector<int>(n);
for (int i = 1; i < n; i++) {
cin >> wait[i] >> speed[i];
}
solve(0);
for (int i = 1; i < n; i++) {
cout << dp[i] << " ";
}
}
