#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#ifdef MY_DEBUG
#include "debug.h"
#endif
#ifdef MY_DEBUG
#define debug(...) \
std::cerr << __LINE__ << ": [", \
__DEBUG_UTIL__::printer(#__VA_ARGS__, __VA_ARGS__)
#define debugArr(...) \
std::cerr << __LINE__ << ": [", \
__DEBUG_UTIL__::printerArr(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...)
#define debugArr(...)
#endif
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define T0(x) get<0>(x)
#define T1(x) get<1>(x)
#define T2(x) get<2>(x)
#define T3(x) get<3>(x)
#define T4(x) get<4>(x)
#define T5(x) get<5>(x)
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> t3;
#define FR(i, n) for (ll i = 0, __nend__##i = ll(n); i < __nend__##i; ++i)
#define FOR(i, a, b) \
for (ll i = (a), __nend__##i = ll(b); i <= __nend__##i; ++i)
#define FORD(i, a, b) \
for (ll i = (a), __nend__##i = ll(b); i >= __nend__##i; --i)
#define v1ll vector<ll>
#define v2ll vector<v1ll>
#define v3ll vector<v2ll>
#define v4ll vector<v3ll>
#define mk_v1ll(n, x) vector<ll>(n, x)
#define mk_v2ll(n, m, x) vector<v1ll>(n, mk_v1ll(m, x))
#define mk_v3ll(n, m, l, x) vector<v2ll>(n, mk_v2ll(m, l, x))
#define mk_v4ll(n, m, l, k, x) vector<v3ll>(n, mk_v3ll(m, l, k, x))
template <typename T>
auto mk_v1(ll n, const T& x) {
return vector<T>(n, x);
}
template <typename T>
auto mk_v2(ll n, ll m, const T& x) {
return vector<vector<T>>(n, mk_v1(m, x));
}
template <typename T>
auto mk_v3(ll n, ll m, ll l, const T& x) {
return vector<vector<vector<T>>>(n, mk_v2(m, l, x));
}
template <typename T>
auto mk_v4(ll n, ll m, ll l, ll k, const T& x) {
return vector<vector<vector<vector<T>>>>(n, mk_v3(m, l, k, x));
}
#define getBit(n, i) (((n) >> (i)) & 1ll)
#define setBit(n, i) ((n) | (1ll << (i)))
#define clearBit(n, i) ((n) & ~(1ll << (i)))
#define flipBit(n, i) ((n) ^ (1ll << (i)))
std::mt19937_64 Rng{static_cast<unsigned long long>(
std::chrono::steady_clock::now().time_since_epoch().count())};
constexpr ll MyP = 1000000021ll;
constexpr ll MyPrime = 1000000033ll;
constexpr ll MyPrime2 = 1000000087ll;
const ld PI = acos(ld(-1));
#define UNUSED(x) (void)x
#define endl '\n'
#ifdef LOCAL
#define cin fin
#endif
template <class T, class T2>
struct PairHash {
std::size_t operator()(const std::pair<T, T2>& p) const {
auto hash1 = std::hash<T>{}(p.first);
auto hash2 = std::hash<T2>{}(p.second);
return hash1 ^ (hash2 + 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2));
}
};
template <class F>
struct __FixPoint : private F {
constexpr __FixPoint(F&& f) : F(std::forward<F>(f)) {}
template <class... T>
constexpr auto operator()(T&&... x) const {
return F::operator()(*this, std::forward<T>(x)...);
}
};
struct __MakeFixPoint {
template <class F>
constexpr auto operator|(F&& f) const {
return __FixPoint<F>(std::forward<F>(f));
}
};
#define __MFP __MakeFixPoint() |
#ifdef __GNUC__
#define __GPOP _Pragma("GCC diagnostic pop") _Pragma("GCC diagnostic pop")
#else
#define __GPOP
#endif
#ifdef __GNUC__
#define def(name, ...) \
_Pragma("GCC diagnostic push") _Pragma( \
"GCC diagnostic ignored \"-Wshadow\"") _Pragma("GCC diagnostic push") \
_Pragma( \
"GCC diagnostic ignored \"-Wunused-but-set-variable\"") auto name = \
__MFP[&](auto&& name, __VA_ARGS__)
#else
#define def(name, ...) auto name = __MFP[&](auto&& name, __VA_ARGS__)
#endif
#ifdef _MSC_VER
#pragma warning(disable : 4996)
#endif
#define REOPEN(input, output) \
freopen(input, "r", stdin); \
freopen(output, "w", stdout);
#define _All(x) (x).begin(), (x).end()
template <class T1, class T2>
bool umin(T1& t1, T2&& t2) {
if (t1 > t2) {
t1 = std::forward<T2>(t2);
return true;
}
return false;
}
template <class T1, class T2>
bool umax(T1& t1, T2&& t2) {
if (t1 < t2) {
t1 = std::forward<T2>(t2);
return true;
}
return false;
}
#define REOPEN(input, output) \
freopen(input, "r", stdin); \
freopen(output, "w", stdout);
#define _All(x) (x).begin(), (x).end()
template <class T>
T f(T x, const v1ll& h, const v1ll& c) {
T ss = 0;
FR(i, h.size()) ss += abs(h[i] - x) * c[i];
return -ss;
};
#include <iostream>
#include <vector>
using namespace std;
namespace line_container_undo {
typedef long long ll;
typedef pair<ll, ll> Line;
const int N = 1e5 + 9;
const ll INF = (ll)1e18;
struct operation {
int pos, top;
Line overwrite;
operation(int _p, int _t, Line _o) {
pos = _p;
top = _t;
overwrite = _o;
}
};
vector<operation> undoLst;
Line lines[N];
int top = 0;
ll eval(Line line, ll x) { return line.first * x + line.second; }
bool bad(Line a, Line b, Line c) {
return (double)(b.second - a.second) / (a.first - b.first) >=
(double)(c.second - a.second) / (a.first - c.first);
}
ll getMin(ll coord) {
int l = 0, r = top - 1;
ll ans = eval(lines[l], coord);
while (l < r) {
int mid = (l + r) >> 1;
ll x = eval(lines[mid], coord);
ll y = eval(lines[mid + 1], coord);
if (x > y)
l = mid + 1;
else
r = mid;
ans = min(ans, min(x, y));
}
return ans;
}
bool insertLine(Line newLine) {
int l = 1, r = top - 1, k = top;
while (l <= r) {
int mid = (l + r) >> 1;
if (bad(lines[mid - 1], lines[mid], newLine)) {
k = mid;
r = mid - 1;
} else
l = mid + 1;
}
undoLst.push_back(operation(k, top, lines[k]));
top = k + 1;
lines[k] = newLine;
return true;
}
void undo() {
operation ope = undoLst.back();
undoLst.pop_back();
top = ope.top;
lines[ope.pos] = ope.overwrite;
}
} // namespace line_container_undo
int main() {
UNUSED(MyPrime);
UNUSED(MyPrime2);
UNUSED(MyP);
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#else
auto startTime = chrono::steady_clock::now();
ifstream fin("_i.txt");
#endif
ll n;
cin >> n;
vector<vector<pll>> g(n);
FR(i, n - 1) {
ll u, v, w;
cin >> u >> v >> w;
u--, v--;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
v1ll s(n), v(n);
FOR(i, 1, n - 1) cin >> s[i] >> v[i];
v1ll depth(n);
v1ll ans(n);
def(dfs, ll u, ll pa, ll dep)->void {
depth[u] = dep;
if (u != 0) {
ans[u] = depth[u] * v[u] + s[u] + line_container_undo::getMin(v[u]);
line_container_undo::insertLine({-depth[u], ans[u]});
} else
line_container_undo::insertLine({0, 0});
for (auto [v, w] : g[u])
if (v != pa) {
dfs(v, u, dep + w);
}
line_container_undo::undo();
};
dfs(0, -1, 0);
FOR(i, 1, n - 1) cout << ans[i] << " ";
#ifdef LOCAL
fin.close();
auto endTime = chrono::steady_clock::now();
auto diff = endTime - startTime;
cerr << endl;
cerr << "Time :" << chrono::duration<double, milli>(diff).count() << " ms"
<< endl;
#endif
return 0;
}
