#include <bits/stdc++.h>
using namespace std;
long long a[200005],b[200005];
vector<int>v[200005];
vector<long long>bq[200005];
int pos[200005],cnt;
bool bi(int x,int y)
{
	return b[x]>b[y];
}
long long dep[200005];
void dfs(int x,int f)
{
	if(f==0)dep[x]=0;
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		dep[v[x][i]]=dep[x]+bq[x][i];
		dfs(v[x][i],x);
	}
}
long long dis[200005];
std::vector<long long> travel(std::vector<long long> A,
        std::vector<int> B, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    int n = A.size();
    for(int i=1;i<=n;i++)a[i]=A[i-1],b[i]=B[i-1];
    int sl=0;
    for(int i=1;i<=n;i++)if(b[i]!=0)sl++;
    for(int i=0;i<n-1;i++)
    {
    	v[U[i]].push_back(V[i]);
    	v[V[i]].push_back(U[i]);
    	bq[U[i]].push_back(W[i]);
    	bq[V[i]].push_back(W[i]);
	}
	dis[1]=0;
	for(int i=2;i<=n;i++)dis[i]=1000000000000000000LL;
    if(sl<=2000)
    {
    	for(int i=1;i<=n;i++)if(b[i]!=0)pos[++cnt]=i;
    	sort(pos+1,pos+cnt+1,bi);
    	for(int ii=1;ii<=cnt;ii++)
    	{
    		int i=pos[ii];
    		if(dis[i]==1000000000000000000LL)continue;
    		dfs(i,0);
    		for(int j=1;j<=n;j++)
    		{
    			dis[j]=min(dis[j],dis[i]+a[i]+b[i]*dep[j]);
			}
		}
		long long minn=1000000000000000000LL;
		for(int i=1;i<=n;i++)if(b[i]==0)minn=min(minn,dis[i]+a[i]);
		for(int i=1;i<=n;i++)dis[i]=min(dis[i],minn);
		vector<long long>qans;
		for(int i=2;i<=n;i++)qans.push_back(dis[i]);
		return qans;
	}
	vector<long long>v;
	for(int i=2;i<=n;i++)v.push_back(0);
	return v;
}