#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ones(n) __builtin_popcount(n)
#define msb(n) (31 - __builtin_clz(n))
#define lsb(n) __builtin_ctz(n)
const int N = 2e5 + 5, M = 1e3 + 5, LOG = 31;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
const ll maxN = 1e7 + 5;
struct Line {
ll m, c;
Line() : m(0), c(llinf) {}
Line(ll m, ll c) : m(m), c(c) {}
};
ll sub(ll x, Line l) {
return x * l.m + l.c;
}
// Persistent Li Chao
struct Node {
// range I am responsible for
Line line;
Node *left, *right;
Node() {
left = right = NULL;
}
Node(ll m, ll c) {
line = Line(m, c);
left = right = NULL;
}
void extend(int l, int r) {
if (left == NULL && l != r) {
left = new Node();
right = new Node();
}
}
Node *copy(Node *node) {
Node *newNode = new Node;
newNode->left = node->left;
newNode->right = node->right;
newNode->line = node->line;
return newNode;
}
Node *add(Line toAdd, int l, int r) {
int mid = (l + r) / 2;
Node *cur = copy(this);
if (l == r) {
if (sub(l, toAdd) < sub(l, cur->line))
swap(toAdd, cur->line);
return cur;
}
bool lef = sub(l, toAdd) < sub(l, cur->line);
bool midE = sub(mid + 1, toAdd) < sub(mid + 1, cur->line);
if (midE)
swap(cur->line, toAdd);
cur->extend(l, r);
if (lef != midE) {
cur->left = cur->left->add(toAdd, l, mid);
} else {
if (mid + 1 > r)
return cur;
cur->right = cur->right->add(toAdd, mid + 1, r);
}
return cur;
}
Node *add(Line toAdd) {
return add(toAdd, -maxN + 1, maxN - 1);
}
ll query(ll x, int l, int r) {
int mid = (l + r) / 2;
if (l == r || left == NULL)
return sub(x, line);
extend(l, r);
if (x <= mid)
return min(sub(x, line), left->query(x, l, mid));
else
return min(sub(x, line), right->query(x, mid + 1, r));
}
ll query(ll x) {
return query(x, -maxN + 1, maxN - 1);
}
void clear() {
if (left != NULL) {
left->clear();
right->clear();
}
delete this;
}
};
Node *tree[N];
int a[N], b[N];
ll dist[N], dp[N];
vector<pair<int, int>> adj[N];
void dfs(int u, int p = 0) {
for (auto [v, w]: adj[u]) {
if (v == p)
continue;
dist[v] = dist[u] + w;
dp[v] = tree[u]->query(b[v]) + dist[v] * b[v] + a[v];
tree[v] = tree[u]->add(Line(-dist[v], dp[v]));
dfs(v, u);
}
}
void testCase() {
int n;
cin >> n;
tree[1] = new Node(0, 0);
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
for (int i = 2; i <= n; i++)
cin >> a[i] >> b[i];
dfs(1);
}
void preCompute() {
}
int32_t main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cout << fixed << setprecision(int32_t(-log10(eps)));
preCompute();
int tc = 1;
// cin >> tc;
for (int TC = 1; TC <= tc; TC++) {
// cout << "Case #" << TC << ": ";
testCase();
}
}
/*
*/
