#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k > o.k; }
	bool operator<(ll x) const { return p < x; }
};
const ll INF = 3e18;
struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		if(empty())return INF;
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};
const ll MAXN = 1e5;
vector <pll> g[MAXN+100];
ll a[MAXN+100],b[MAXN+100];
ll full_sz;
ll sz[MAXN+100];
ll pa[MAXN+100];
LineContainer s[MAXN+100];
vector <pll> anc[MAXN+100];
ll dist[MAXN+100];
bool del[MAXN+100];
ll order[MAXN+100];
void dfs_sz(ll u,ll p){
    sz[u] = 1;
    for (auto tmp:g[u]){
        ll v = tmp.fi;
        if (v == p || del[v])continue;
        dfs_sz(v,u);
        sz[u] += sz[v];
    }
}
ll f(ll u,ll p){
    for (auto tmp:g[u]){
        ll v = tmp.fi;
        if (del[v] || v == p)continue;
        if (sz[v] * 2 > full_sz){
            return f(v,u);
        }
    }
    return u;
}
ll find_centroid(ll u){
    dfs_sz(u,u);
    full_sz = sz[u];
    return f(u,u);
}
void dfs_dist(ll u,ll p,ll root){
//    cout<<u<<' '<<p<<' '<<root<<endl;
    if (u == p)dist[u] = 0;
    anc[u].push_back(MP(root,dist[u]));
    for (auto tmp:g[u]){
        ll v = tmp.fi;
        if (v == p || del[v])continue;
        dist[v] = dist[u] + tmp.se;
        dfs_dist(v,u,root);
    }
}
void solve(ll u,ll p){
    pa[u] = p;
    u = find_centroid(u);
    dfs_dist(u,u,u);

    {
        del[u] = 1;
        for (auto v:g[u]){
            if (!del[v.fi])solve(v.fi,u);
        }
    }
}
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 = sz(A);
    for (ll i = 0;i < n - 1;i ++){
        g[U[i]+1].push_back(MP(V[i]+1,W[i]));
        g[V[i]+1].push_back(MP(U[i]+1,W[i]));
    }
    for (ll i = 0;i < n;i ++)a[i+1] = A[i],b[i+1] = B[i];
    solve(1,1);
    iota(order+1,order+1+n,1);
    sort(order+1,order+1+n,[&](ll x,ll y){return b[x] > b[y];});
    vector <ll> ans(n-1);
    for (ll i = 1;i <= n;i ++){
        ll id = order[i];
        ll res = INF;
        if (id==1)res = 0;
        else {
            for (auto x:anc[id]){
                res = min(res,s[x.fi].query(x.se));
            }
        }
        if (id >= 2)ans[id-2]=res;
        for (auto x:anc[id]){
//            cout<<id<<' '<<x.se<<' '<<b[id]<<' '<<res+a[id]+b[id]*x.se<<'\n';
            s[x.fi].add(b[id],res+a[id]+b[id]*x.se);
        }
    }
    for (ll i = 1;i <= n;i ++){
        ll id = order[i];
        ll res = INF;
        if (id==1)res = 0;
        else {
            for (auto x:anc[id]){
                res = min(res,s[x.fi].query(x.se));
            }
        }
        if (id >= 2)ans[id-2]=min(ans[id-2],res);
    }
    return ans;
}