#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;
const int LB = 17 + 2;
const ll linf = 0x3f3f3f3f3f3f3f3f;

struct Line
{
	ll k,b;
	Line(void){}
	Line(ll _k,ll _b): k(_k), b(_b) {}
	ll get(ll x) const { return k * x + b;}
};

struct SegT
{
	vector<ll> xs;
	vector<Line> tree;
	#define ls(u) ((u)<<1)
	#define rs(u) ((u)<<1|1)
	#define lson(u) ls(u),l,mid
	#define rson(u) rs(u),mid+1,r
	void init(const vector<ll> &_xs)
	{
		xs = _xs;
		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());
		tree.resize((int)xs.size() * 4 + 1, Line(0, linf));
	}
	void insert(int u,int l,int r,Line k)
	{
		int mid = (l+r)>>1;
		if(k.get(xs[mid]) < tree[u].get(xs[mid])) swap(tree[u], k);
		if(l == r) return;
		if(k.get(xs[l]) < tree[u].get(xs[l])) insert(lson(u), k);
		if(k.get(xs[r]) < tree[u].get(xs[r])) insert(rson(u), k);
	}
	ll query(int u,int l,int r,int i)
	{
		ll res = tree[u].get(xs[i]);
		if(l == r) return res;
		int mid = (l+r)>>1;
		return min(res, i <= mid? query(lson(u),i): query(rson(u),i));
	}
	void insert(Line k)
	{
		insert(1, 0, (int)xs.size() - 1, k);
	}
	ll query(ll x)
	{
		int i = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
		return query(1, 0, (int)xs.size() - 1, i);
	}
};

int n;
ll a[MAXN], b[MAXN];
vector<pii> g[MAXN];

int anct[MAXN][LB], dept[MAXN];
ll dist[MAXN][LB];
vector<int> nodest[MAXN];
SegT tree[MAXN];

namespace Divid
{
	bool fob[MAXN];
	int siz[MAXN], mxson[MAXN], rt, totsiz;
	vector<int> nodes;
	void dfs_siz(int u,int fa)
	{
		siz[u] = 1; mxson[u] = 0;
		nodes.emplace_back(u);
		for(auto it: g[u]) if(it.first != fa && !fob[it.first])
		{
			int v = it.first;
			dfs_siz(v, u);
			siz[u] += siz[v];
			mxson[u] = max(mxson[u], mxson[v]);
		}
	}
	ll dis[MAXN];
	void dfs_dis(int u,int fa)
	{
		for(auto it: g[u]) if(it.first != fa && !fob[it.first])
		{
			int v = it.first;
			dis[v] = dis[u] + it.second;
			dfs_dis(v,u);
		}
	}
	void divid(int u,int k)
	{
		nodes.clear();
		dfs_siz(u,0);
		rt = u; totsiz = siz[u];
		for(int v: nodes)
		{
			mxson[v] = max(mxson[v], totsiz - siz[v]);
			if(mxson[v] < mxson[rt]) rt = v;
		}
		rt = u; fob[u] = 1;
		
//		printf("divid:\n");
//		printf("rt = %d\n",u);
//		printf("nodes: ");
//		for(auto v: nodes)
//			printf("%d ",v);
//		printf("\n");
		
		dis[u] = 0;
		dfs_dis(u,0);
		
		dept[u] = k;
		for(int v: nodes)
		{
			anct[v][k] = u;
			dist[v][k] = dis[v];
		}
		
		sort(nodes.begin(), nodes.end(), [&] (int x,int y){
			return dis[x] > dis[y];
		});
		nodest[u] = nodes;
		
		vector<ll> xs;
		for(auto v: nodes)
			xs.emplace_back(dis[v]);
		tree[u].init(xs);
		
		for(auto it: g[u]) if(!fob[it.first])
			divid(it.first, k + 1);
	}
}

ll f[MAXN];
bool vis[MAXN];
priority_queue< pair<ll,int> > q;

void fl(int u)
{
	auto &vec = nodest[u];
	while(vec.size() && vis[vec.back()]) vec.pop_back();
	if(!vec.size()) return;
	int v = vec.back();
	ll cur = tree[u].query(dist[v][dept[u]]);
	if(cur < f[v])
	{
		f[v] = cur;
		q.emplace(-f[v], v);
	}
}

vector<ll> travel(vector<ll> _a, vector<int> _b, vector<int> _u, vector<int> _v, vector<int> _w)
{
	n = (int)_a.size();
	for(int i=1; i<=n; ++i)
		a[i] = _a[i-1], b[i] = _b[i-1];
	for(int i=0; i<n-1; ++i)
	{
		int u = _u[i] + 1, v = _v[i] + 1, w = _w[i];
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	
	Divid :: divid(1, 0);
	
	memset(f, 0x3f, sizeof(f));
	f[1] = 0;
	q.emplace(0, 1);
	while(q.size())
	{
		int u = q.top().second; q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		
		for(int i=0; i<=dept[u]; ++i)
		{
			int v = anct[u][i];
			tree[v].insert(Line(b[u], f[u] + a[u] + b[u] * dist[u][i]));
			fl(v);
		}
	}
	
	return vector<ll>(f+2, f+n+1);
}