#include <bits/stdc++.h>
using namespace std;
long long a[200005],b[200005];
vector<int>v[200005];
vector<long long>bq[200005];
int df[200005];
int fa[200005][19],dep[200005];
long long het[200005];
void dfs(int x,int f)
{
	dep[x]=dep[f]+1;
	fa[x][0]=f;
	for(int i=1;i<=18;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		het[v[x][i]]=het[x]+bq[x][i];
		dfs(v[x][i],x); 
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=18;i>=0;i--)
	{
		if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	}
	if(x==y)return x;
	for(int i=18;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int finddis(int x,int y)
{
	return het[x]+het[y]-2*het[lca(x,y)];
}
int sum,nrt;
int siz[200005],sy[200005],rf[100005];
bool vis[200005];
void findrt(int x,int f)
{
	rf[x]=f;
	siz[x]=1;
	sy[x]=0;
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f||vis[v[x][i]])continue;
		findrt(v[x][i],x);
		siz[x]+=siz[v[x][i]];
		sy[x]=max(sy[x],siz[v[x][i]]);
	}
	sy[x]=max(sy[x],sum-siz[x]);
	if(sy[x]<sy[nrt])nrt=x;
}
int rt[200005];
int ch[4000005][2];
long long nk[4000005],nb[4000005];
int cnt;
bool vist[4000005];
void insert(int& k,long long l,long long r,long long tk,long long tb)
{
	if(k==0)k=++cnt;
	if(vist[k]==false)
	{
		vist[k]=true;
		nk[k]=tk;
		nb[k]=tb;
		return;
	}
	long long mid=((l+r)>>1);
	long long pz=nk[k]*mid+nb[k],xz=tk*mid+tb;
	if(xz<pz)
	{
		swap(nk[k],tk);
		swap(nb[k],tb);
		swap(xz,pz);
	}
	if(l==r)return;
	if(tk<nk[k])insert(ch[k][1],mid+1,r,tk,tb);
	else insert(ch[k][0],l,mid,tk,tb);
}
long long query(int k,long long l,long long r,long long x)
{
	if(k==0||!vist[k])return 1000000000000000000LL;
	long long ans=nk[k]*x+nb[k];
	if(l==r)return ans;
	long long mid=((l+r)>>1);
	if(x<=mid)ans=min(ans,query(ch[k][0],l,mid,x));
	else ans=min(ans,query(ch[k][1],mid+1,r,x));
	return ans;
}
void solve(int x)
{
	if(rf[x]!=0&&vis[rf[x]]==false)siz[rf[x]]=sum-siz[x];
	vis[x]=true;
	for(int i=0;i<v[x].size();i++)
	{
		if(vis[v[x][i]])continue;
		sum=siz[v[x][i]];
		nrt=0;
		findrt(v[x][i],0);
		df[nrt]=x;
		solve(nrt);
	}
}
int pos[200005];
long long dis[200005];
bool bi(int x,int y)
{
	return b[x]>b[y];
}
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)
{
    int n = A.size();
    for(int i=1;i<=n;i++)
    {
    	a[i]=A[i-1];
    	b[i]=B[i-1];
    	pos[i]=i;
	}
	sort(pos+1,pos+n+1,bi);
    for(int i=0;i<n-1;i++)
    {
    	U[i]++;
    	V[i]++;
    	v[U[i]].push_back(V[i]);
    	v[V[i]].push_back(U[i]);
    	bq[U[i]].push_back(W[i]);
    	bq[V[i]].push_back(W[i]);
	}
	dfs(1,0);
	printf("orz\n");
	nrt=0;
	sum=n;
	sy[0]=1000000000;
	findrt(1,0);
	df[nrt]=0;
	solve(nrt);
	for(int i=1;i<=n;i++)printf("%d ",df[i]);
	printf("\n");
	dis[1]=0;
	for(int i=2;i<=n;i++)dis[i]=1000000000000000000LL;
	for(int ii=1;ii<=n;ii++)
	{
		int i=pos[ii];
		int now=i;
		while(now!=0)
		{
			dis[i]=min(dis[i],query(rt[now],1,1000000000000LL,finddis(i,now)));
			now=df[now];
		}
		if(dis[i]==1000000000000000000LL)continue;
		now=i;
		while(now!=0)
		{
			insert(rt[now],1,1000000000000LL,b[i],dis[i]+a[i]+b[i]*finddis(i,now));
			now=df[now];
		}
	}
	for(int i=1;i<=n;i++)
	{
		int now=i;
		while(now!=0)
		{
			dis[i]=min(dis[i],query(rt[now],1,1000000000000LL,finddis(i,now)));
			now=df[now];
		}
	}
	vector<long long>qans;
	for(int i=2;i<=n;i++)qans.push_back(dis[i]); 
    return qans;
}