#include <bits/stdc++.h>

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]);
        }
    }
    {
        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);
}