#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(!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[x],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||!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;
}
//int main () {
// freopen("taxi.in","r",stdin);
// freopen("taxi.out","w",stdout);
// int n; scanf("%d",&n); vector<LL> A; vector<int> B,U,V,W;
// for(int i=1;i<=n;++i) { LL x; scanf("%lld",&x); A.pb(x); }
// for(int i=1;i<=n;++i) { int x; scanf("%d",&x); B.pb(x); }
// for(int i=1;i<n;++i) { int u,v,w; scanf("%d%d%d",&u,&v,&w); U.pb(u); V.pb(v); W.pb(w); }
// vector<LL> ANS=travel(A,B,U,V,W);
// for(auto t:ANS) printf("%lld\n",t);
// return 0;
//}