#include<bits/stdc++.h>
#define Yzl unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define lob lower_bound
#define pb emplace_back
typedef long long LL;

using namespace std;

const Yzl Lty=20120712;

const int MAXN=1e5+10;
const LL P=1e12,inf=8e18;
int n;
struct ddl {
	LL a,b,i;
}a[MAXN],b[MAXN];
vector<pi> e[MAXN];
void add(int f,int t,int c) {
	e[f].pb(mp(t,c));
}
int FA[MAXN][20],dep[MAXN],Fa[MAXN];
LL dt[MAXN];
void dfs(int u,int fa) {
	FA[u][0]=fa; dep[u]=dep[fa]+1; for(int i=1;i<=19;++i) FA[u][i]=FA[FA[u][i-1]][i-1];
	for(auto t:e[u]) if(t.fi!=fa) dt[t.fi]=dt[u]+t.se,dfs(t.fi,u);
}
int LCA(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;--i) if(dep[FA[x][i]]>=dep[y]) x=FA[x][i];
	if(x==y) return x;
	for(int i=19;i>=0;--i) if(FA[x][i]!=FA[y][i]) x=FA[x][i],y=FA[y][i];
	return FA[x][0];
}
LL get_dt(int x,int y) { int lca=LCA(x,y);
	return dt[x]+dt[y]-(dt[lca]<<1);
}
int sz[MAXN],maxn[MAXN],rt;
bool vis[MAXN];
void get_rt(int u,int fa,int total) {
	sz[u]=1; maxn[u]=0;
	for(auto t:e[u]) if(t.fi!=fa&&!vis[t.fi]) {
		get_rt(t.fi,u,total); sz[u]+=sz[t.fi]; maxn[u]=max(maxn[u],sz[t.fi]);
	} maxn[u]=max(maxn[u],total-sz[u]);
	if(maxn[u]<maxn[rt]) rt=u;
}
void solve(int u,int fa,int S) {
	rt=0; get_rt(u,0,S); u=rt; vis[u]=1; Fa[u]=fa;
	for(auto t:e[u]) if(!vis[t.fi]) {
		if(sz[t.fi]<sz[u]) solve(t.fi,u,sz[t.fi]);
		else solve(t.fi,u,S-sz[u]);
	}
}
const int M=1e7+10;
int RT[MAXN];
struct line {
	LL k,b;
};
bool chk(line a,line b,LL x) {
	return a.k*x+a.b<b.k*x+b.b;
}
LL get_val(line a,LL x) {
	return a.k*x+a.b;
}
struct SGT {
	int ls[M],rs[M],cnt;
	line tr[M]; bool vis[M];
	void update(int &u,LL l,LL r,line x) { if(l>r) return ;
		if(!u) {
			u=++cnt;
			if(cnt>1e7) {
				cout<<l<<" "<<r<<endl;
				exit(0);
			}
		}
		if(!vis[u]) return tr[u]=x,vis[u]=1,void();
		LL mid=(l+r)>>1; if(!chk(tr[u],x,mid)) swap(tr[u],x);
		if((chk(tr[u],x,l)&&chk(tr[u],x,r))||(l==r)) return ; 
		if(!chk(tr[u],x,l)) update(ls[u],l,mid,x);
		if(!chk(tr[u],x,r)) update(rs[u],mid+1,r,x);
	}
	LL query(int u,LL l,LL r,LL x) { if(l>r||!vis[u]) return inf;
		LL res=get_val(tr[u],x); if(l==r) return res;
		LL mid=(l+r)>>1;
		if(x<=mid) res=min(res,query(ls[u],l,mid,x));
		else res=min(res,query(rs[u],mid+1,r,x));
		return res;
	}
}T;
LL dis[MAXN];
void UPD(int u) {
	for(int i=u;i;i=Fa[i]) {
		T.update(RT[i],1,P,(line){b[u].b,dis[u]+b[u].a+get_dt(u,i)*b[u].b});
	}
}
LL QUE(int u) { LL res=inf;
	for(int i=u;i;i=Fa[i]) {
		res=min(res,T.query(RT[i],1,P,get_dt(u,i)));
	}
	return res;
}
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]=(ddl){A[i-1],B[i-1],i},b[i]=a[i];
	for(int i=0;i<n-1;++i) { ++U[i]; ++V[i]; add(U[i],V[i],W[i]); add(V[i],U[i],W[i]); }
	maxn[0]=Lty; solve(1,0,n); dfs(1,0); sort(a+1,a+1+n,[&](ddl a,ddl b){return a.b>b.b;});
	memset(dis,127,sizeof(dis)); dis[1]=0; UPD(1);
	for(int i=1;i<=n;++i) { if(a[i].i==1) continue;
		LL res=QUE(a[i].i); dis[a[i].i]=res; 
		UPD(a[i].i);
	} for(int i=2;i<=n;++i) dis[i]=min(dis[i],QUE(i));
	vector<LL> ANS; for(int i=2;i<=n;++i) ANS.pb(dis[i]);
	return ANS;
}