#include <vector>
#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
using namespace std;
const int N=1e5+10,lgN=20;
const i128 lnf=1e18+10;
int n;
i128 a[N],b[N];
vector<pair<int,i128> > e[N];
i128 dp[N];

int sd[N],bt[N][lgN];
i128 dis[N][lgN];
bool vis[N];
int tot,sum[N],mxsum[N];
void getrt(int x,int fa,int &rt) {
	sum[x]=1,mxsum[x]=0;
	for(auto v:e[x]) if(v.first!=fa&&!vis[v.first]) {
		getrt(v.first,x,rt);
		sum[x]+=sum[v.first];
		mxsum[x]=max(mxsum[x],sum[v.first]);
	}
	mxsum[x]=max(mxsum[x],tot-sum[x]);
	if(mxsum[x]<mxsum[rt]) rt=x;
}
void fixsum(int x,int fa) {
	sum[x]=1;
	for(auto v:e[x]) if(v.first!=fa&&!vis[v.first]) {
		fixsum(v.first,x);
		sum[x]+=sum[v.first];
	}
}
int st[N],stt;
void getdis(int dep,int x,int fa,i128 d) {
	st[++stt]=x;
	dis[x][dep]=d;
	for(auto v:e[x]) if(v.first!=fa&&!vis[v.first]) {
		getdis(dep,v.first,x,d+v.second);
	}
}
void calc(int dep,int rt) {
	sd[rt]=dep;
	st[stt=1]=rt;
	dis[rt][dep]=0;
	bt[rt][dep]=rt;
	for(auto x:e[rt]) if(!vis[x.first]) {
		int hd=stt;
		getdis(dep,x.first,rt,x.second);
		for(int i=hd+1;i<=stt;i++) bt[st[i]][dep]=rt;
	}
}
void solve(int dep,int x) {
	assert(dep<20);
	int rt=0;
	getrt(x,0,rt);
	// cerr<<x<<' '<<rt<<"\n";
	fixsum(rt,0);
	vis[rt]=1;
	for(auto v:e[rt]) if(!vis[v.first]) {
		tot=sum[v.first];
		solve(dep+1,v.first);
	}
	vis[rt]=0;
	calc(dep,rt);
}

#define vec pair<i128,i128>
vec operator + (vec x,vec y) {
	return make_pair(x.first+y.first,x.second+y.second);
}
vec operator - (vec x,vec y) {
	return make_pair(x.first-y.first,x.second-y.second);
}
i128 operator ^ (vec x,vec y) {
	return x.first*y.second-x.second*y.first;
}
vector<vec> sta[N];
#define tp(id) (sta[id].size())
#define X(i,j) (sta[i][j].first)
#define Y(i,j) (sta[i][j].second)
bool check(vec x,vec y) {
	return (x^y)>0;
}
void update(int id,i128 x,i128 y) {
	auto cur=make_pair(x,y);
	if(tp(id)>0&&sta[id][tp(id)].first==x) {
		y=min(y,sta[id][tp(id)].second);
		sta[id].pop_back();
	}
	while(tp(id)>1&&
		!check(sta[id][tp(id)-1]-sta[id][tp(id)-2],
		cur-sta[id][tp(id)-1])) {
		sta[id].pop_back();
	}
	sta[id].emplace_back(cur);
}
// bool deb;
i128 query(int id,i128 k) {
	if(sta[id].empty()) return lnf;
	int res=0,l=1,r=tp(id)-1;
	vec tmp=make_pair(1,k);
	while(l<=r) {
		int mid=(l+r)/2;
		if(check(sta[id][mid]-sta[id][mid-1],tmp)) res=mid,l=mid+1;
		else r=mid-1;
	}
	i128 ans=sta[id][res].second-k*sta[id][res].first;
	return ans;
}
void Upd(int x) {
	for(int i=sd[x];i>=1;i--) {
		update(bt[x][i],-b[x],dp[x]+a[x]+b[x]*dis[x][i]);
	}
}
i128 Qry(int x) {
	i128 Ans=lnf;
	for(int i=sd[x];i>=1;i--) {
		Ans=min(Ans,query(bt[x][i],dis[x][i]));
	}
	return Ans;
}

int p[N];
i128 Ans[N];

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)
{
	n=A.size();
	for(int i=1;i<=n;i++) a[i]=A[i-1];
	for(int i=1;i<=n;i++) b[i]=B[i-1];
	for(int i=0;i<n-1;i++) {
		e[U[i]+1].emplace_back(V[i]+1,W[i]);
		e[V[i]+1].emplace_back(U[i]+1,W[i]);
	}
	for(int i=1;i<=n;i++) dp[i]=lnf,p[i]=i;
	dp[1]=0;
	sort(p+1,p+1+n,[&](int x,int y) {
		return b[x]>b[y];
	});
	tot=n;
	mxsum[0]=0x3f3f3f3f;
	// cerr<<"OK\n";
	solve(1,1);
	// cerr<<"OK\n";
	// for(int i=1;i<=n;i++,cerr<<'\n') 
	// 	for(int j=sd[i];j>=1;j--) cerr<<bt[i][j]<<' ';
	for(int i=1;i<=n;i++) {
		// cerr<<p[i]<<":\n";
		dp[p[i]]=min(dp[p[i]],Qry(p[i]));
		// cerr<<"OK\n";
		Upd(p[i]);
		// cerr<<dp[p[i]]<<"\n";
	}
	// for(int i=1;i<=n;i++) {
	// 	for(auto j:sta[i]) cerr<<"("<<j.first<<','<<j.second<<")";
	// 	cerr<<"\n";
	// }
	// deb=1;
	for(int i=1;i<=n;i++) Ans[i]=Qry(i);
	vector<ll> RES(n-1);
	for(int i=2;i<=n;i++) RES[i-2]=Ans[i];
	return RES;
}

/*
cd "D:\OI\4 NOI\Counting_And_DP\QOJ6660\cpp"
g++ taxi.cpp grader.cpp -o taxi -std=c++14 -Wall -O2
./taxi 
*/