#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
constexpr ll inf = (1ll<<60);
vi solve_subtask_1_3_4(std::vector<long long> A,
std::vector<int> B, std::vector<int> U, std::vector<int> V, std::vector<int> W){
ll N = A.size();
vii edge(N), weight(N);
rep(i,0,N-1){
edge[U[i]].pb(V[i]);
edge[V[i]].pb(U[i]);
weight[U[i]].pb(W[i]);
weight[V[i]].pb(W[i]);
}
vi ans(N,inf);
ans[0] = 0;
std::map<ll,vi> mem;
rep(i,0,N){
mem[-B[i]].pb(i);
}
for(auto el__: mem){
vi v = el__.second;
ll b = -el__.first;
vi dist(N, inf);
std::priority_queue<pii> que;
for(auto el: v){
if(ans[el] == inf) continue;
dist[el] = ans[el]+A[el];
que.push(mp(-dist[el], el));
}
while(!que.empty()){
auto el = que.top(); que.pop();
ll now = el.second;
if(-el.first > dist[now]) continue;
rep(i,0,edge[now].size()){
ll next = edge[now][i];
if(dist[next] > dist[now]+b*weight[now][i]){
dist[next] = dist[now]+b*weight[now][i];
que.push(mp(-dist[next], next));
}
}
}
rep(i,0,N) ans[i] = std::min(ans[i], dist[i]);
}
{
reverse(all(ans));
ans.pop_back();
reverse(all(ans));
}
return ans;
}
vi solve_subtask_2(std::vector<long long> A,
std::vector<int> B, std::vector<int> U, std::vector<int> V, std::vector<int> W){
ll N = A.size();
std::deque<ll> a,b;
ll dist = 0;
a.pb(A[0]);
b.pb(B[0]);
vi ans(N);
rep(i,1,N){
dist += W[i-1];
while(a.size() > 1){
ll n = a.size();
if(b[n-1]*dist+a[n-1] > b[n-2]*dist+a[n-2]){
a.pop_back();
b.pop_back();
}
else break;
}
ans[i] = b.back()*dist+a.back();
if(b[0] > B[i]){
b.emplace_front(B[i]);
a.emplace_front(ans[i]+A[i]-dist*B[i]);
}
else if(b[0] == B[i]){
a[0] = std::min(a[0], ans[i]+A[i]-dist*B[i]);
}
}
{
reverse(all(ans));
ans.pop_back();
reverse(all(ans));
}
return ans;
}
std::vector<long long> travel(std::vector<long long> A,
std::vector<int> B, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
ll N = A.size();
bool flag = true;
rep(i,0,N-1){
if(U[i] != i || V[i] != i+1) flag = false;
}
if(flag) return solve_subtask_2(A,B,U,V,W);
else return solve_subtask_1_3_4(A,B,U,V,W);
}