#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#define N 1000000
#define inf 2e18
#define INF 1e9
using namespace std;
struct node
{
    int num,data,snum;
};
struct reads
{
    int num;
    long long data;
    bool operator < (const reads &t)const
    {
	return data>t.data;
    }
};
struct points
{
    int x;
    long long y;
    bool operator < (const points &t)const
    {
	return x!=t.x?x<t.x:y<t.y;
    }
};
int n,cater,length,rt,sx,sy,smz,szt,nums,ds,fa[N+1],b[N+1],sz[N+1],maxp[N+1],ls[N+1],rs[N+1],ps[N+1],ps2[N+1],minn;
long long a[N+1],dis[N+1],depth[N+1];
bool used[N+1],vis[N+1],vst[N+1];
vector<node>E[N+1];
vector<node>ES[N+1];
vector<reads>A[N+1];
vector<reads>B[N+1];
vector<long long>depths[N+1];
set<points>s1[N+1];
set<points>s2[N+1];
priority_queue<reads>q;
void add(int x,int y,int z,int w)
{
    E[x].push_back((node){y,z,w}),E[y].push_back((node){x,z,w});
    return;
}
void add2(int x,int y,int z)
{
    ++cater,ES[x].push_back((node){y,z,cater}),ES[y].push_back((node){x,z,cater});
    return;
}
void dfs(int x)
{
    int nw=0;
    vis[x]=1;
    for (int i=0;i<E[x].size();++i)
	if (!vis[E[x][i].num])
	{
	    dfs(E[x][i].num),++length,add2(length,E[x][i].num,E[x][i].data);
	    if (nw) add2(length,nw,0);
	    nw=length;
	}
    if (nw) add2(x,nw,0);
    vis[x]=0;
    return;
}
void get_rt(int x)
{
    vis[x]=sz[x]=1;
    for (int i=0;i<ES[x].size();++i)
	if (!used[ES[x][i].snum]&&!vis[ES[x][i].num])
	{
	    get_rt(ES[x][i].num),sz[x]+=sz[ES[x][i].num];
	    if (max(sz[ES[x][i].num],smz-sz[ES[x][i].num])<minn) minn=max(sz[ES[x][i].num],smz-sz[ES[x][i].num]),sx=x,sy=ES[x][i].num,nums=ES[x][i].snum,ds=ES[x][i].data,szt=sz[ES[x][i].num];
        }
    vis[x]=0;
    return;
}
void dfs2(int x)
{
    if (x<=n) depths[x].push_back(depth[x]),A[length].push_back((reads){x,depth[x]});
    vis[x]=1;
    for (int i=0;i<ES[x].size();++i)
	if (!used[ES[x][i].snum]&&!vis[ES[x][i].num])
	    depth[ES[x][i].num]=depth[x]+ES[x][i].data,dfs2(ES[x][i].num);
    vis[x]=0;
    return;
}
void dfs3(int x)
{
    if (x<=n) depths[x].push_back(depth[x]),B[length].push_back((reads){x,depth[x]});
    vis[x]=1;
    for (int i=0;i<ES[x].size();++i)
	if (!used[ES[x][i].snum]&&!vis[ES[x][i].num])
	    depth[ES[x][i].num]=depth[x]+ES[x][i].data,dfs3(ES[x][i].num);
    vis[x]=0;
    return;
}
bool cmp(reads a,reads b)
{
    return a.data<b.data;
}
int solve(int x,int y)
{
    int d1=smz-szt,d2=szt,nw=++length;
    used[nums]=1,depth[x]=ds,depth[y]=0,dfs2(x),dfs3(y),sort(A[nw].begin(),A[nw].end(),cmp),sort(B[nw].begin(),B[nw].end(),cmp);
    smz=d1,minn=INF;
    if (smz!=1) get_rt(x),ls[nw]=solve(sx,sy);
    else ls[nw]=x;
    smz=d2,minn=INF;
    if (smz!=1) get_rt(y),rs[nw]=solve(sx,sy);
    else rs[nw]=y;
    fa[ls[nw]]=fa[rs[nw]]=nw;
    return nw;
}
bool check(points a,points b,points c)
{
    return 1ll*(b.y-a.y)*(c.x-a.x)>=1ll*(c.y-a.y)*(b.x-a.x);
}
void get(int x,int k,long long b)
{
    while (s1[x].size()>=2)
    {
	auto it=s1[x].lower_bound((points){k,b});
	if (it!=s1[x].end())
	{
	    auto it2=it;
	    it2++;
	    if (it2!=s1[x].end())
	    {
		if (check((points){k,b},*it,*it2)) s1[x].erase(it);
		else break;
	    }
	    else break;
	}
	else break;
    }
    while (s1[x].size()>=2)
    {
	auto it=s1[x].lower_bound((points){k,b});
	if (it!=s1[x].begin())
	{
	    it--;
	    if (it!=s1[x].begin())
	    {
		auto it2=it;
		it2--;
		if (check(*it2,*it,(points){k,b})) s1[x].erase(it);
		else break;
	    }
	    else break;
	}
	else break;
    }
    s1[x].insert((points){k,b});
    return;
}
void get2(int x,int k,long long b)
{
    while (s2[x].size()>=2)
    {
	auto it=s2[x].lower_bound((points){k,b});
	if (it!=s2[x].end())
	{
	    auto it2=it;
	    it2++;
	    if (it2!=s2[x].end())
	    {
		if (check((points){k,b},*it,*it2)) s2[x].erase(it);
		else break;
	    }
	    else break;
	}
	else break;
    }
    while (s2[x].size()>=2)
    {
	auto it=s2[x].lower_bound((points){k,b});
	if (it!=s2[x].begin())
	{
	    it--;
	    if (it!=s2[x].begin())
	    {
		auto it2=it;
		it2--;
		if (check(*it2,*it,(points){k,b})) s2[x].erase(it);
		else break;
	    }
	    else break;
	}
	else break;
    }
    s2[x].insert((points){k,b});
    return;
}
long long query(int x,long long d)
{
    long long res=inf;
    for (auto it:s1[x]) res=min(res,1ll*it.x*d+it.y);
    return res;
    if (s1[x].empty()) return inf;
    while (s1[x].size()>=2)
    {
	auto it=s1[x].end();
	it--;
	auto it2=it;
	it2--;
	if (check(*it2,*it,(points){1,-d})) s1[x].erase(it);
	else break;
    }
    auto it=s1[x].end();
    it--;
    return 1ll*(*it).x*d+(*it).y;
}
long long query2(int x,long long d)
{
    long long res=inf;
    for (auto it:s2[x]) res=min(res,1ll*it.x*d+it.y);
    return res;
    if (s2[x].empty()) return inf;
    while (s2[x].size()>=2)
    {
	auto it=s2[x].end();
	it--;
	auto it2=it;
	it2--;
	if (check(*it2,*it,(points){1,-d})) s2[x].erase(it);
	else break;
    }
    auto it=s2[x].end();
    it--;
    return 1ll*(*it).x*d+(*it).y;
}
void adder(int x)
{
    int y=x,cl;
    long long d;
    for (int i=(int)(depths[x].size())-1;i>=0;--i)
    {
	cl=(rs[fa[y]]==y),y=fa[y];
	if (!cl) get2(y,b[x],dis[x]+a[x]+1ll*b[x]*depths[x][i]);
	else get(y,b[x],dis[x]+a[x]+1ll*b[x]*depths[x][i]);
	while (ps[y]<A[y].size()&&vst[A[y][ps[y]].num]) ps[y]++;
	if (ps[y]<A[y].size())
	{
	    d=query(y,A[y][ps[y]].data);
	    if (d<dis[A[y][ps[y]].num]) dis[A[y][ps[y]].num]=d,q.push((reads){A[y][ps[y]].num,d});
	}
	while (ps2[y]<B[y].size()&&vst[B[y][ps2[y]].num]) ps2[y]++;
	if (ps2[y]<B[y].size())
	{
	    d=query2(y,B[y][ps2[y]].data);
	    if (d<dis[B[y][ps2[y]].num]) dis[B[y][ps2[y]].num]=d,q.push((reads){B[y][ps2[y]].num,d});
	}
    }
    return;
}
void dijkstra()
{
    int top;
    for (int i=1;i<=n;++i) dis[i]=inf;
    dis[1]=0,q.push((reads){1,0});
    while (!q.empty())
    {
	top=q.top().num,q.pop();
	if (vst[top]) continue;
	vst[top]=1,adder(top);
    }
    return;
}
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)
{
    length=n=A.size();
    vector<long long>qry(n-1);
    for (int i=1;i<=n;++i) a[i]=A[i-1],b[i]=B[i-1];
    for (int i=1;i<=n-1;++i) add(U[i-1]+1,V[i-1]+1,W[i-1],i);
    dfs(1);
    smz=length,minn=INF,get_rt(1),rt=solve(sx,sy),dijkstra();
    for (int i=2;i<=n;++i) qry[i-2]=dis[i];
    return qry;
}