#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = (int)3e5;
struct Line {
LL a,b;
Line (LL a = 0,LL b = LLONG_MAX) : a(a) , b(b) {};
LL F(LL x){
return a*x + b;
}
};
struct State{
int size;
int add_pos;
Line val;
};
struct CHT{
public:
long double get_intersec(Line x,Line y){
return (long double)(y.b - x.b) / (x.a - y.a);
}
vector<Line> line;
vector<State> order;
int cur_size = 0;
void reload_size(int n){
line = vector<Line>(n+3,Line());
cur_size = 0;
return;
}
void add_line(Line x){
int low = 1 , high = cur_size - 1;
int pos = cur_size;
while (low<=high){
int mid = (low+high)/2;
if (get_intersec(line[mid - 1] , line[mid]) >= get_intersec(line[mid] , x)){
pos = mid;
high = mid - 1;
}
else low = mid + 1;
}
order.push_back({cur_size , pos , line[pos]});
cur_size = pos + 1;
line[pos] = x;
return;
}
LL Get(LL x){
int low = 1 , high = cur_size - 1 , pos = 0;
while (low<=high){
int mid = (low+high)/2;
if (get_intersec(line[mid-1],line[mid]) <= x){
pos = mid;
low = mid + 1;
}
else high = mid-1;
}
return line[pos].F(x);
}
void rollback(void){
if (order.size()==0) return;
int size = order.back().size;
int pos = order.back().add_pos;
Line val = order.back().val;
cur_size = size; line[pos] = val;
order.pop_back();
return ;
}
};
CHT baoloi;
int n;
LL d[N+2] , dp[N+2];
int st[N+2] , speed[N+2];
vector<pair<int,int>>ke[N+2];
void add_canh(int u,int v,int w){
ke[u].push_back({v,w}) ,
ke[v].push_back({u,w});
return;
}
void dfs(int u,int p = 0){
if (p==0) dp[u] = 0; else {
dp[u] = st[u] + d[u] * speed[u] + baoloi.Get(speed[u]);
}
baoloi.add_line(Line(-d[u] , dp[u]));
for(auto&v:ke[u]){
if (v.first==p) continue;
d[v.first] = d[u] + v.second;
dfs(v.first , u);
}
baoloi.rollback();
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0) ;
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin>>n;
for(int i = 1; i < n; ++i) {
int u,v,w; cin>>u>>v>>w;
add_canh(u,v,w);
}
baoloi.reload_size(n);
for(int i = 2; i <= n; ++i) cin>>st[i]>>speed[i];
dfs(1);
for(int i = 2; i <= n; ++i) cout<<dp[i]<<' '; cout<<'\n';
return 0;
}
