#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);


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();
    vii edge(N), weight(N), d_edge(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 dist(N, -1), par(N), hld_dist(N);
    {
        std::queue<ll> que;
        vector<bool> visited(N);
        dist[0] = 0;
        que.push(0);
        while(!que.empty()){
            ll now = que.front(); que.pop();
            rep(i,0,edge[now].size()){
                ll next = edge[now][i];
                if(dist[next] != -1) continue;
                dist[next] = dist[now]+weight[now][i];
                que.push(next);
                d_edge[now].pb(next);
                hld_dist[next] = hld_dist[now]+1;
            }
        }
    }
    vi c_par(N,-1);
    vector<bool> dead(N);

    vi subtree(N);

    std::function<void(ll)> calc_subtree = [&](ll now){
        subtree[now] = 1;
        for(auto next: d_edge[now]){
            if(dead[next]) continue;
            calc_subtree(next);
            subtree[now] += subtree[next];
        }
    };

    // hld

    vi hld_par(N);

    std::function<void(ll)> heavy_light_decomposition = [&](ll now){
        rep(i,1,d_edge[now].size()){
            if(subtree[edge[now][0]] < subtree[edge[now][i]]) std::swap(edge[now][i], edge[now][0]);
        }
        rep(i,0,d_edge[now].size()){
            ll next = d_edge[now][i];
            if(i) hld_par[next] = next;
            else hld_par[next] = hld_par[now];
            par[next] = now;
            heavy_light_decomposition(next);
        }
    };

    auto LCA = [&](ll l, ll r){
        while(true){
            if(hld_par[l] == hld_par[r]){
                if(hld_dist[l] < hld_dist[r]) std::swap(l,r);
                return r;
            }
            if(hld_dist[hld_par[l]] < hld_dist[hld_par[r]]) std::swap(l,r);
            l = par[hld_par[l]];
        }
    };

    auto distance = [&](ll l, ll r){
        return dist[l]+dist[r]-2*dist[LCA(l,r)];
    };

    calc_subtree(0);
    heavy_light_decomposition(0);

    // centroid tree
    
    std::function<ll(ll, ll)> find_centroid = [&](ll root, ll now){
        ll max = subtree[root]-subtree[now];
        for(auto next: d_edge[now]){
            if(dead[next]) continue;
            ll c = find_centroid(root, next);
            if(c != -1) return c;
            max = std::max(max, subtree[next]);
        }
        if(max*2 <= subtree[root]) return now;
        return ll(-1);
    };
    std::function<void(ll,ll)> centroid_coloring = [&](ll centroid, ll now){
        if(now != centroid) c_par[now] = centroid;
        for(auto next: d_edge[now]){
            if(dead[next]) continue;
            centroid_coloring(centroid, next);
        }
    };

    std::function<void(ll)> dfs_centroid_decomposition = [&](ll root){
        if(dead[root]) return;
        calc_subtree(root);
        if(subtree[root] == 1) return;
        ll c = find_centroid(root,root);
        centroid_coloring(c, root);
        dead[c] = true;
        for(auto next: d_edge[c]){
            dfs_centroid_decomposition(next);
        }
        dfs_centroid_decomposition(root);
    };

    dfs_centroid_decomposition(0);

    vector<pii> data(N);
    rep(i,0,N) data[i] = mp(B[i], i);
    sort(all(data));
    reverse(all(data));

    vector<vector<pii>> lines(N);

    // m について判定
    // is_need : true → m は必要
    auto is_need = [&](pii l, pii m, pii r){
        return ((r.second-m.second)*(m.first-l.first) <= (m.second-l.second)*(r.first-m.first));
    };

    auto add_line = [&](ll idx, pii l){
        /*if(!lines[idx].empty() && lines[idx].back().first == l.first){
            ll n = lines[idx].size();
            if(lines[idx][n-1].second <= l.second) return;
            lines[idx].pop_back();
        }*/

        while(lines[idx].size() > 1){
            ll n = lines[idx].size();
            if(!is_need(lines[idx][n-2], lines[idx][n-1], l)) lines[idx].pop_back();
            else break;
        }

        lines[idx].pb(l);
    };

    auto value = [&](pii f, ll x){
        return f.first*x+f.second;
    };

    auto calc = [&](ll idx, ll x){
        if(lines[idx].empty()) return inf;
        {
            ll min = inf;
            for(auto el: lines[idx]){
                min = std::min(min, value(el, x));
                //cout << value(el, x) << " ";
            }
            //cout << endl;
            return min;
        }
        ll left = 0, right = lines[idx].size();
        while(left+1 < right){
            ll mid = (left+right)/2;
            if(value(lines[idx][mid-1],x) > value(lines[idx][mid], x)) left = mid;
            else right = mid;
        }
        return value(lines[idx][left], x);
    };

    vi ans(N, inf);
    ans[0] = 0;

    for(auto el: data){
        ll now = el.second;
        ll n_v = now;
        while(true){
            ans[now] = std::min(ans[now], calc(n_v, distance(now, n_v)));
            if(c_par[n_v] == -1) break;
            n_v = c_par[n_v];
        }
        n_v = now;
        while(true){
            add_line(n_v, mp(B[now], A[now]+ans[now]+distance(now, n_v)*B[now]));
            if(c_par[n_v] == -1) break;
            n_v = c_par[n_v];
        }
    }
    rep(now,0,N){
        ll n_v = now;
        while(true){
            ans[now] = std::min(ans[now], calc(n_v, distance(now, n_v)));
            if(c_par[n_v] == -1) break;
            n_v = c_par[n_v];
        }
    }
    {
        reverse(all(ans));
        ans.pop_back();
        reverse(all(ans));
    }
    return ans;
}