#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

struct node{
	ll k,b;
	node(ll k=0,ll b=0):k(k),b(b){}
}line[2000005];

int n,tot,fs,mn,rt,ncnt,cnt,cur;
int v[200005],nxt[200005],h[100005],siz[100005],lch[6000005],rch[6000005],tag[6000005],dep[100005],pl[100005],f[100005],trt[100005];
ll c[200005],val[20][100005],a[100005],b[100005],dis[100005];
bool vis[100005],hv[100005];
vector<pll> vec[100005];
vector<int> inq[100005];
priority_queue<pll,vector<pll>,greater<pll> > q;

void addedge(int x,int y,ll z){
	v[++tot]=y; c[tot]=z; nxt[tot]=h[x]; h[x]=tot;
	v[++tot]=x; c[tot]=z; nxt[tot]=h[y]; h[y]=tot;
}

void getsize(int u,int fa){
	siz[u]=1;
	for(int p=h[u];p;p=nxt[p]){
		if(v[p]==fa||vis[v[p]]) continue;
		getsize(v[p],u);
		siz[u]+=siz[v[p]];
	}
}

void getroot(int u,int fa){
	int mx=0;
	for(int p=h[u];p;p=nxt[p]){
		if(v[p]==fa||vis[v[p]]) continue;
		getroot(v[p],u);
		chkmax(mx,siz[v[p]]);
	}
	if(chkmin(mn,max(mx,fs-siz[u]))) rt=u;
}

void dfs(int u,int fa){
	vec[rt].pb(mp(val[cur][u],u));
	for(int p=h[u];p;p=nxt[p]){
		if(v[p]==fa||vis[v[p]]) continue;
		val[cur][v[p]]=val[cur][u]+c[p];
		dfs(v[p],u);
	}
}

void solve(int u){
	vis[u]=1;
	getsize(u,-1);
	cur=dep[u];
	val[cur][u]=0;
	dfs(u,-1);
	sort(vec[u].begin(),vec[u].end());
	for(int p=h[u];p;p=nxt[p]){
		if(vis[v[p]]) continue;
		fs=siz[v[p]],mn=n,rt=0;
		getroot(v[p],-1);
		dep[rt]=dep[u]+1;
		// adj[u].pb(rt);
		f[rt]=u;
		solve(rt);
	}
}

ll get(int x,ll y){return line[x].k*y+line[x].b;}

void change(int &id,int l,int r,int c,int t){
	if(!id) id=++ncnt;
	if(!tag[id]) return (void)(tag[id]=c);
	if(l==r){
		if(get(tag[id],vec[t][l-1].fi)>get(c,vec[t][l-1].fi)) tag[id]=c;
		return;
	}
	int mid=(l+r)/2;
	if(line[tag[id]].k<line[c].k){
		if(get(tag[id],vec[t][mid-1].fi)>get(c,vec[t][mid-1].fi)) change(rch[id],mid+1,r,tag[id],t),tag[id]=c;
		else change(lch[id],l,mid,c,t);
	}
	else{
		if(get(tag[id],vec[t][mid-1].fi)>get(c,vec[t][mid-1].fi)) change(lch[id],l,mid,tag[id],t),tag[id]=c;
		else change(rch[id],mid+1,r,c,t);
	}
}

ll query(int id,int l,int r,int x,int t){
	if(!id) return 1ll<<60;
	if(l==r) return get(tag[id],vec[t][x-1].fi);
	int mid=(l+r)/2;
	if(x<=mid) return min(get(tag[id],vec[t][x-1].fi),query(lch[id],l,mid,x,t));
	else return min(get(tag[id],vec[t][x-1].fi),query(rch[id],mid+1,r,x,t));
}

ll calc(int x,int y){
	ll res=query(trt[x],1,siz[x],y+1,x);
	return res;
}

void init(){
	for(int i=1;i<=n;i++){
		if(pl[i]<vec[i].size()){
			ll tmp=calc(i,pl[i]);
			if(chkmin(dis[vec[i][pl[i]].se],tmp)) q.push(mp(tmp,vec[i][pl[i]].se));
			inq[vec[i][pl[i]].se].pb(i);
		}
	}
}

void push(int x){
	ll d=dis[x],ta=a[x],tb=b[x],bef=x;
	// cout<<"push "<<x<<' '<<dis[x]<<endl;
	while(x){
		line[++cnt]=node(tb,ta+d+tb*val[dep[x]][bef]);
		change(trt[x],1,siz[x],cnt,x);
		if(pl[x]<vec[x].size()){
			ll tmp=calc(x,pl[x]);
			// cout<<"pushto "<<x<<' '<<vec[x][pl[x]].se<<' '<<tmp<<' '<<line[cnt].k<<' '<<line[cnt].b<<' '<<endl;
			if(chkmin(dis[vec[x][pl[x]].se],tmp)) q.push(mp(tmp,vec[x][pl[x]].se));
		}
		x=f[x];
	}
}

void pop(int x){
	for(auto r:inq[x]){
		while(pl[r]<vec[r].size()&&hv[vec[r][pl[r]].se]) pl[r]++;
		if(pl[r]<vec[r].size()){
			ll tmp=calc(r,pl[r]);
			// cout<<"popto "<<r<<' '<<vec[r][pl[r]].se<<' '<<tmp<<endl;
			if(chkmin(dis[vec[r][pl[r]].se],tmp)) q.push(mp(tmp,vec[r][pl[r]].se));
			inq[vec[r][pl[r]].se].pb(r);
		}
	}
	inq[x].clear();
}

vector<ll> travel(vector<ll> A,vector<int> B,vector<int> U,vector<int> V,vector<int> W){
	n=A.size();
	for(int i=0;i<n;i++) a[i+1]=A[i],b[i+1]=B[i];
	for(int i=0;i<n-1;i++) addedge(U[i]+1,V[i]+1,W[i]);
	getsize(1,-1);
	fs=n,mn=n,rt=0;
	getroot(1,-1);
	solve(rt);
	for(int i=1;i<=n;i++) dis[i]=1ll<<60;
	dis[1]=0;
	init();
	push(1);
	hv[1]=1;
	while(!q.empty()){
		int t=q.top().se; q.pop();
		if(hv[t]) continue;
		hv[t]=1;
		pop(t);
		push(t);
	}
	vector<ll> ret;
	for(int i=2;i<=n;i++) ret.pb(dis[i]);
	// for(int i=2;i<=n;i++) cout<<dis[i]<<' ';
	// cout<<endl;
	return ret;
}