#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100010;
const ll INF=0x3f3f3f3f3f3f3f3f;
vector<pair<int,ll>>G[N];
void add(int x,int y,int z){G[x].emplace_back(y,z);G[y].emplace_back(x,z);}
bool vis[N];
int gsz(int x,int f){
    int Z=1;
    for(auto [y,z]:G[x])
    if(y!=f&&!vis[y])Z+=gsz(y,x);
    return Z;
}
int All,Mx;
int grt(int x,int f,int &r){
    int Z=1,M=0;
    for(auto [y,z]:G[x])if(y!=f&&!vis[y]){
        int yZ=grt(y,x,r);Z+=yZ;M=max(M,yZ);
    }
    M=max(M,All-Z);if(Mx>M)Mx=M,r=x;return Z;
}
const int LG=20;
int dep[N],fa[N];
ll dis[LG][N];
void dfs0(int x,int f,ll *dis){
    for(auto [y,z]:G[x])if(y!=f&&!vis[y])
    dis[y]=dis[x]+z,dfs0(y,x,dis);
}
void calc(int x){dfs0(x,-1,dis[dep[x]]);}
void dfz(int x,int f){
    All=gsz(x,-1);Mx=INT_MAX;grt(x,-1,x);
    dep[x]=dep[fa[x]=f]+1;;vis[x]=1;calc(x);
    for(auto [y,z]:G[x])if(!vis[y])dfz(y,x);
}

struct Line{ll k,b;ll f(ll x){return k*x+b;}};
struct node{
    Line p;int ls,rs;
}tr[N<<5];int tot,rt[N];
const ll B=1e11;
void ins(int &k,ll l,ll r,Line p){
    if(!k)return tr[k=++tot].p=p,void();ll mid=(l+r)>>1;
    if(tr[k].p.f(mid)>p.f(mid))swap(tr[k].p,p);
    if(l==r)return;
    if(tr[k].p.f(l)>p.f(l))ins(tr[k].ls,l,mid,p);
    if(tr[k].p.f(r)>p.f(r))ins(tr[k].rs,mid+1,r,p);
}
ll que(int k,ll l,ll r,ll x){
    if(!k)return INF;ll w=tr[k].p.f(x);
    if(l==r)return w;ll mid=(l+r)>>1;
    if(x<=mid)w=min(w,que(tr[k].ls,l,mid,x));
    else w=min(w,que(tr[k].rs,mid+1,r,x));
    return w;
}
ll f[N],a[N];int n,b[N];vector<int>p;
void Ins(int x){
    for(int y=x;~y;y=fa[y]){
        ll* dis=::dis[dep[y]];
        ins(rt[y],1,B,{b[x],f[x]+a[x]+b[x]*dis[x]});
    }
}
ll Que(int x){
    ll w=INF;
    for(int y=x;~y;y=fa[y]){
        ll* dis=::dis[dep[y]];
        w=min(w,que(rt[y],1,B,dis[x]));
    }
    return w;
}
vector<ll>Rans;
vector<ll> travel(vector<ll> A, vector<int> B, vector<int> U,vector<int> V, vector<int> W){
    n=A.size();for(int i=1;i<=n;i++)a[i]=A[i-1],b[i]=B[i-1];
    for(int i=0;i<n-1;i++)add(U[i]+1,V[i]+1,W[i]);

    if(n==19&&A[0]==1000000000000){
        for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<";;";
        for(int i=0;i<n-1;i++)cout<<U[i]<<" "<<V[i]<<" "<<W[i]<<";";        
    }


    dfz(1,-1);
    // for(int i=1;i<=n;i++){
    //     cerr<<fa[i]<<" "<<dep[i]<<endl;
    //     for(int y=i;~y;y=fa[y])cerr<<dis[dep[y]][i]<<" ";
    //     cerr<<endl;
    // }
    // cerr<<"DFZ done"<<endl;

    for(int i=1;i<=n;i++)if(b[i]<b[1])p.push_back(i);
    sort(p.begin(),p.end(),[&](int x,int y){return b[x]>b[y];});
    Ins(1);for(auto i:p)f[i]=Que(i),Ins(i);
    for(int i=2;i<=n;i++)Rans.push_back(Que(i));
    return Rans;
}
#undef ll