/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <chrono>
#include <vector>
#define maxn 200005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define PB push_back
#define X first
#define Y second
#define control cout<<"passed"<<endl;
typedef unsigned long long ull;
typedef std::pair <int, int> pii;
typedef long long ll;
typedef std::pair <ll, ll> pll;
typedef std::pair <int, ll> pil;
typedef std::pair <ll, int> pli;
typedef long double ld;
std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}
struct CHT
{
std::vector <pii> hull;
ll calc(pii curr, ll x)
{
return curr.X * x + curr.Y;
}
double intersection(pii a, pii b)
{
return (double)(b.Y - a.Y) / (a.X - b.X);
}
void add_line(pii curr)
{
while(hull.size() >= 2)
{
if(intersection(hull[hull.size() - 2], hull.back()) >= intersection(hull.back(), curr))
hull.pop_back();
else
break;
}
hull.PB(curr);
}
ll query(double x)
{
if(hull.size() == 0)
return 1e18;
int l = 0, r = hull.size() - 1;
while(l < r)
{
ll mid = (l + r) / 2;
if(calc(hull[mid], x) > calc(hull[mid + 1], x))
l = mid + 1;
else
r = mid;
}
return calc(hull[l], x);
}
};
std::vector <pii> v[maxn];
int depth[maxn], sz[maxn], up[maxn], lead[maxn];
std::vector <int> d[maxn];
int dist[maxn];
void dfs_sz(int node, int par)
{
d[depth[node]].PB(node);
up[node] = par;
sz[node] = 1;
for(auto& nb : v[node])
{
if(nb.X == par)
continue;
depth[nb.X] = depth[node] + 1;
dist[nb.X] = dist[node] + nb.Y;
dfs_sz(nb.X, node);
sz[node] += sz[nb.X];
}
}
int heavy[maxn];
int cnt = 0;
void dfs_hld(int node, int par, int le)
{
cnt++;
if(cnt > 15)
exit(0);
//std::cout << node << " " << par << " " << le << "\n";
lead[node] = le;
heavy[node] = -1;
for(auto& nb : v[node])
{
if(nb.X == par)
continue;
if(heavy[node] == -1 || (sz[nb.X] > sz[heavy[node]] && nb.X != par))
heavy[node] = nb.X;
}
//std::cout << "!! " << heavy[node] << "\n";
if(heavy[node] == -1)
return;
dfs_hld(heavy[node], node, le);
for(auto& nb : v[node])
if(nb.X != par && nb.X != heavy[node])
dfs_hld(nb.X, node, nb.X);
}
CHT h[maxn];
ll speed[maxn], wait[maxn];
ll answer(int node)
{
//std::cout << "------------------------------" << "\n";
//std::cout << node << "\n";
ll ans = 1e18;
int start = node;
while(node != 1)
{
/**std::cout << node << "\n";
std::cout << h[lead[node]].query(speed[start]) << "\n";
std::cout << "!!!!!" << "\n" << speed[node] << ": ";
for(auto& e : h[lead[node]].hull)
std::cout << "{ " << e.X << " " << e.Y << " } ";
std::cout << "\n";
std::cout << "!!!!!" << "\n";*/
ans = std::min(ans, h[lead[node]].query(speed[start]));
node = lead[node];
if(node == 1)
break;
node = up[node];
}
return ans;
}
int n;
ll dp[maxn];
void read()
{
std::cin >> n;
for(int i = 1; i <= n - 1; i++)
{
int x, y, z;
std::cin >> x >> y >> z;
v[x].PB({y, z});
v[y].PB({x, z});
}
for(int i = 1; i <= n - 1; i++)
std::cin >> wait[i + 1] >> speed[i + 1];
depth[1] = 0;
dfs_sz(1, 0);
//std::cout << "here" << "\n";
dfs_hld(1, 0, 1);
//std::cout << "here" << "\n";
dp[1] = 0;
for(int i = 1; i <= n - 1; i++)
{
//std::cout << "****************************" << "\n";
for(auto& node : d[i])
{
dp[node] = wait[node] + speed[node] * dist[node];
//std::cout << "?------? " << node << " " << answer(node) << " " << dist[node] * speed[node] + wait[node] << "\n";
dp[node] = std::min(dp[node], answer(node) + dist[node] * speed[node] + wait[node]);
}
for(auto& node : d[i])
h[lead[node]].add_line({-dist[node], dp[node]});
}
for(int i = 2; i <= n; i++)
std::cout << dp[i] << " ";
std::cout << "\n";
}
int main()
{
/**#ifdef ONLINE_JUDGE /// promeni
freopen("taxi.in", "r", stdin);
freopen("taxi.out", "w", stdout);
#endif*/
//std::ios_base::sync_with_stdio(false);
//std::cin.tie(nullptr);
startT = std::chrono::high_resolution_clock::now();
read();
return 0;
}
