#include <bits/stdc++.h>
#define double long double
#define int long long
#ifdef zhr_debug
#define debug printf
#else
void debug(const char* s,...){}
#endif
using namespace std;
const int inf=1000000000000000000ll;
void freopen(string file){freopen((file+".in").c_str(),"r",stdin);freopen((file+".out").c_str(),"w",stdout);}
int n;
int a[100020];
int b[100020];
struct edge
{
int to,val;
edge(int to=0,int val=0):to(to),val(val){}
};
vector<edge> e[100020];
int fa[100020][20];
int dep[100020];
int dis[100020];
int sz[100020];
bool vis[100020];
void findrt(int x,int f,int all,int &rt)
{
sz[x]=1;
int mx=0;
for(edge v:e[x])
{
if(vis[v.to] || v.to==f) continue;
findrt(v.to,x,all,rt);
sz[x]+=sz[v.to];
mx=max(mx,sz[v.to]);
}
mx=max(mx,all-sz[x]);
if(mx<=n/2) rt=x;
}
int top[100020];
void dfs1(int x,int f)
{
fa[x][0]=f;for(int i=1;i<=17;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
dep[x]=dep[f]+1;
for(edge v:e[x])
{
if(v.to==f) continue;
dis[v.to]=dis[x]+v.val;
dfs1(v.to,x);
}
}
int getlca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=17;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=17;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int getdis(int x,int y){return dis[x]+dis[y]-2*dis[getlca(x,y)];}
void dfs2(int x,int f,int all)
{
findrt(x,0,all,x);
findrt(x,0,all,x);
debug("dfs2(%lld)\n",x);
top[x]=f;
vis[x]=true;
for(edge v:e[x])
{
if(vis[v.to] || v.to==f) continue;
dfs2(v.to,x,sz[v.to]);
}
}
int o[100020];
int dp[100020];
struct node
{
int x,y;
node(int x=0,int y=0):x(x),y(y){}
};
double slope(node a,node b){return 1.0L*(a.y-b.y)/(a.x-b.x);}
struct ConvexHull
{
vector<node> hull;
void insert(node a)
{
if(hull.size() && hull.back().x==a.x)
{
a.y=min(a.y,hull.back().y);
hull.pop_back();
}
while(hull.size()>1 && slope(hull[hull.size()-1],hull[hull.size()-2])<=slope(hull[hull.size()-1],a)) hull.pop_back();
hull.push_back(a);
}
int query(int k)
{
if(hull.empty()) return inf;
k=-k;
static int l,r,mid,res;
l=1;r=hull.size()-1;res=0;
while(l<=r)
{
mid=(l+r)>>1;
if(slope(hull[mid],hull[mid-1])>k) res=mid,l=mid+1;
else r=mid-1;
}
return hull[res].y-hull[res].x*k;
}
};
ConvexHull hull[100020];
void work(int x)
{
debug("work(%lld)\n",x);
if(x==1) dp[x]=0;
else
{
dp[x]=inf;
for(int xx=x;xx;xx=top[xx])
{
dp[x]=min(dp[x],hull[xx].query(getdis(x,xx)));
debug("query : %lld=%lld\n",getdis(x,xx),hull[xx].query(getdis(x,xx)));
}
}
debug("dp[%lld]=%lld\n",x,dp[x]);
for(int xx=x;xx;xx=top[xx])
{
hull[xx].insert(node(b[x],dp[x]+a[x]+b[x]*getdis(x,xx)));
debug("insert : (%lld,%lld+%lld+%lld*%lld)\n",b[x],dp[x],a[x],b[x],getdis(x,xx));
}
}
vector<int> travel(vector<int> A,vector<signed> B,vector<signed> U,vector<signed> V,vector<signed> W)
{
n=A.size();
for(int i=0;i<n;i++) a[i+1]=A[i];
for(int i=0;i<n;i++) b[i+1]=B[i];
for(int i=0;i<n-1;i++)
{
e[U[i]+1].push_back(edge(V[i]+1,W[i]));
e[V[i]+1].push_back(edge(U[i]+1,W[i]));
}
dfs1(1,0);
dfs2(1,0,n);
debug("top : ");for(int i=1;i<=n;i++) debug("%lld ",top[i]);debug("\n");
debug("dis : ");for(int i=1;i<=n;i++) debug("%lld ",dis[i]);debug("\n");
for(int i=1;i<=n;i++) o[i]=i;
sort(o+1,o+n+1,[](int x,int y){return b[x]>b[y];});
for(int i=1;i<=n;i++) work(o[i]);
vector<int> ans;
for(int i=2,tmp;i<=n;i++)
{
tmp=inf;
for(int xx=i;xx;xx=top[xx]) tmp=min(tmp,hull[xx].query(getdis(i,xx)));
ans.push_back(tmp);
}
return ans;
}
signed main()
{
vector<int> res=travel({10,5,13,4,3},{10,7,5,9,1},{1,0,3,2},{0,2,2,4},{1,5,10,3});
for(int x:res) printf("%lld ",x);
}