#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#include<cassert>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(((long long)(n))-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define pb push_back
#define mk make_pair
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
typedef long long i64;
typedef long double f80;
typedef unsigned int u32;
typedef unsigned long long u64;
//typedef __int128 i128;
//typedef unsigned __int128 u128;
/*#ifndef ONLINE_JUDGE
	FILE *___=freopen(".in","r",stdin);
#endif*/
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
int n,m,i,j;
i64 a[100005];int b[100005];
vector<pair<int,int> > bi[100005];
i64 dis[100005];
priority_queue<pair<i64,int> > pq;
int vis[100005],sz[100005],mx[100005],rt,ddp[100005],dfa[100005];
i64 dds[18][100005];vector<pair<i64,int> > vd[100005];int ptr[100005];
void dfs_sz(int x,int fa)
{
	sz[x]=1;ff(bi[x],it)if(it->first!=fa&&!vis[it->first])dfs_sz(it->first,x),sz[x]+=sz[it->first];
}
void dfs_rt(int x,int fa,int all)
{
	mx[x]=all-sz[x];ff(bi[x],it)if(it->first!=fa&&!vis[it->first])dfs_rt(it->first,x,all),mx[x]=max(mx[x],sz[it->first]);
	if(rt==-1||mx[x]<mx[rt])rt=x;
}
void dfs_dis(int x,int fa,i64 ds,int d)
{
	dds[d][x]=ds;vd[rt].push_back(make_pair(ds,x));
	ff(bi[x],it)if(it->first!=fa&&!vis[it->first])dfs_dis(it->first,x,ds+it->second,d);
}
int dfs(int x,int d)
{
	dfs_sz(x,0);rt=-1;dfs_rt(x,0,sz[x]);vis[x=rt]=1;ddp[x]=d;
	dfs_dis(x,0,0,d);sort(vd[x].begin(),vd[x].end());
	ff(bi[x],it)if(!vis[it->first])dfa[dfs(it->first,d+1)]=x;
	return x;
}
struct lne
{
	int x;i64 y;
	i64 f(i64 k){return x*k+y;}
}tr[8000005];
int rrt[100005],lc[8000005],rc[8000005],cur,cnt;
void update(int &x,int l,int r,lne t)
{
	if(!x){x=++cnt;tr[x]=t;return;}int mid=(l+r)/2;
	i64 vl=vd[cur][l].first,vm=vd[cur][mid].first,vr=vd[cur][r].first;
	if(tr[x].f(vl)>t.f(vl)) swap(tr[x],t);
	if(tr[x].f(vm)>t.f(vm)) swap(tr[x],t),update(lc[x],l,mid,t);
	if(tr[x].f(vr)>t.f(vr)) update(rc[x],mid+1,r,t);
}
i64 query(int x,int l,int r,int p)
{
	if(!x) return 0x3f3f3f3f3f3f3f3fll;
	i64 res=tr[x].f(vd[cur][p].first);if(l==r) return res;
	int mid=(l+r)/2;if(p<=mid)res=min(res,query(lc[x],l,mid,p));else res=min(res,query(rc[x],mid+1,r,p));
	return res;
}
void insert(int x,i64 a,int b)
{
	cur=x;lne t=(lne){b,a};
	update(rrt[x],0,vd[x].size()-1,t);
}
void flush(int x)
{
	cur=x;while(ptr[x]<vd[x].size()&&vis[vd[x][ptr[x]].second])ptr[x]++;
	if(ptr[x]<vd[x].size()) pq.push(make_pair(-query(rrt[x],0,vd[x].size()-1,ptr[x]),vd[x][ptr[x]].second));
}
void update(int x,i64 a,int b)
{
	int d=ddp[x],y=x;
	while(y){
		insert(y,a+1ll*b*dds[d][x],b);
		flush(y);
		y=dfa[y];d--;
	}	
}
void dijkstra()
{
	memset(vis,0,sizeof(vis));
	while(!pq.empty()){
		int x=pq.top().second;i64 d=pq.top().first*(-1);pq.pop();
		if(vis[x])continue;vis[x]=1;dis[x]=d;
		update(x,dis[x]+a[x],b[x]);
	}
}
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();fz1(i,n)a[i]=A[i-1],b[i]=B[i-1];fz0k(i,U.size())bi[U[i]+1].push_back(make_pair(V[i]+1,W[i])),bi[V[i]+1].push_back(make_pair(U[i]+1,W[i]));
	memset(dis,0x3f,sizeof(dis));dis[1]=0;pq.push(make_pair(0,1));
	dfs(1,0);
	dijkstra();
	vector<long long> res;fz(i,2,n)res.push_back(dis[i]);return res;
}