#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

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; }
};

struct CHT : 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) {
        k=-k, m=-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=100005, inf=1e18;
CHT S[maxn];
vector <pll> anc[maxn], A[maxn];
ll child[maxn], used[maxn], dis[maxn];

void getchild(ll u, ll pa)
{
    child[u]=1;
    for (auto [v, w]:A[u])
        if (v!=pa && !used[v])
            getchild(v, u), child[u]+=child[v];
}

ll getcentroid(ll u, ll pa, ll n)
{
    for (auto [v, w]:A[u])
        if (v!=pa && !used[v] && child[v]*2>n)
            return getcentroid(v, u, n);
    return u;
}

void dfs(ll u, ll pa, ll r, ll dis)
{
    anc[u].pb({r, dis});
    for (auto [v, w]:A[u])
        if (v!=pa && !used[v])
            dfs(v, u, r, dis+w);
}

void build(ll u)
{
    getchild(u, u), u=getcentroid(u, u, child[u]);
    dfs(u, u, u, 0), used[u]=1;
    for (auto [v, w]:A[u]) if (!used[v]) build(v);
}

vector<ll> travel(vector <ll> a, vector<int> b, vector<int> U, vector<int> V, vector<int> W)
{
    ll n=sz(a);
    for (ll i=0; i<sz(W); i++)
        A[U[i]].pb({V[i], W[i]}), A[V[i]].pb({U[i], W[i]});
    for (ll i=1; i<n; i++) dis[i]=inf; build(0);
    auto getdis=[&](ll u)
    {
        for (auto [r, d]:anc[u])
            dis[u]=min(dis[u], S[r].query(d));
        return dis[u];
    };
    auto propagate=[&](ll u)
    {
        getdis(u);
        for (auto [r, d]:anc[u])
            S[r].add(b[u], dis[u]+a[u]+d*b[u]);
    };
    vector <ll> num(n);
    iota(num.begin(), num.end(), 0);
    sort(num.begin(), num.end(), [&](ll x, ll y){return b[x]>b[y];});
    for (ll i:num) propagate(i);
    vector <ll> ans(n-1);
    for (ll i=0; i<sz(ans); i++) ans[i]=getdis(i+1);
    return ans;
}