#include<bits/stdc++.h>
using namespace std;
using i64=long long;
constexpr i64 V=1e12;
struct E_{int v,w;};
struct L_{i64 k,b;i64 calc(i64 x){return k*x+b;}};
vector<E_>G[100010];
namespace ds1{
	constexpr int N=2500010;
	L_ f[N];
	int tot,ls[N],rs[N];
	void insert(int&u,i64 l,i64 r,L_ x){
	   if(!u)return f[u=++tot]=x,void();
	   if(l==r)return;
	   i64 mid=l+r>>1;
	   if(x.calc(mid)<f[u].calc(mid))swap(x,f[u]);
	   if(x.k<f[u].k)insert(rs[u],mid+1,r,x);
	   else insert(ls[u],l,mid,x);
	}
	i64 query(int u,i64 l,i64 r,i64 p){
	   if(!u)return 1e18;
	   i64 mid=l+r>>1;
	   return min(f[u].calc(p),p<=mid?query(ls[u],l,mid,p):query(rs[u],mid+1,r,p)); 
	}
}
namespace ds2{
	int sz[100010],mxsz[100010],vis[100010],root[100010],R,N;
	struct I_{int rt;i64 d;};
	vector<I_>a[100010];
	void dfs1(int u,int fa){
	   sz[u]=1,mxsz[u]=0;
	   for(E_ e:G[u]){
	      int v=e.v;
	      if(v!=fa&&!vis[v]){
	         dfs1(v,u),sz[u]+=sz[v],mxsz[u]=max(mxsz[u],sz[v]);
	      }
	   }
	   mxsz[u]=max(mxsz[u],N-sz[u]);
	   if(R==-1||mxsz[u]<mxsz[R])R=u;
	}
	void dfs2(int u,int fa,i64 d){
	   a[u].push_back({R,d});
	   for(E_ e:G[u]){
	      int v=e.v,w=e.w;
	      if(v!=fa&&!vis[v])dfs2(v,u,d+w);
	   }
	}
	int getR(int u){N=sz[u],R=-1,dfs1(u,-1);return R;}
	void build(int u){
	   vis[u]=1,R=u,dfs2(u,-1,0);
	   for(E_ e:G[u])if(!vis[e.v])build(getR(e.v));
	}
	void init(){build(getR(1));}
	void insert(int u,L_ x){
	   for(I_ w:a[u])ds1::insert(root[w.rt],0,V,{x.k,x.b+x.k*w.d});
	}
	i64 query(int u){
	   i64 res=1e18;
	   for(I_ w:a[u])res=min(res,ds1::query(root[w.rt],0,V,w.d));
	   return res;
	}
}
vector<i64>travel(vector<i64>A,vector<int>B,vector<int>U,vector<int>V,vector<int>W){
   int n=A.size();
   for(int i=0;i<n-1;i++){
      G[U[i]].push_back({V[i],W[i]});
      G[V[i]].push_back({U[i],W[i]});
   }
   ds2::init();
   vector<int>p(n);
   iota(begin(p),end(p),0);
   sort(begin(p),end(p),[&](int x,int y){return B[x]>B[y];});
   for(int u:p){
      i64 f=u==0?0:ds2::query(u);
      ds2::insert(u,{B[u],A[u]+f});
   }
   vector<i64>ans(n-1);
   for(int i=1;i<n;i++)ans[i-1]=ds2::query(i);
   return ans;
}