#include<bits/stdc++.h>
#define ll long long
#define M 100005
using namespace std;
const ll V = 1e12;
vector<pair<ll, ll> > v[M], F[M];
ll vis[M], sz[M], maxsz[M], minn, nrt, tot;
void dfs1(int x, int fa, int dep, int rt)
{
	F[x].push_back({rt, dep});
	for(auto t : v[x]) if(!vis[t.first] && t.first != fa) dfs1(t.first, x, dep + t.second, rt);
}
void dfs2(int x, int fa)
{
	sz[x] = 1;
	maxsz[x] = 0;
	for(auto t : v[x]) if(!vis[t.first] && t.first != fa)
	{
		dfs2(t.first, x);
		sz[x] += sz[t.first];
		maxsz[x] = max(maxsz[x], sz[t.first]);
	}
//	cout << x << " " << tot << " " << sz[x] << " " << maxsz [ x ] << endl ;
	maxsz[x] = max(maxsz[x], tot - sz[x]);
	if(maxsz[x] < minn) minn = maxsz[x], nrt = x;
}
void csz(int x, int fa)
{
	sz[x] = 1;
	for(auto t : v[x]) if(!vis[t.first] && t.first != fa)
	{
		csz(t.first, x);
		sz[x] += sz[t.first];
	}
}
void dfs(ll x)
{
	cout << x << endl;
	vis[x] = 1;
	dfs1(x, -1, 0, x);
	for(auto t : v[x])
	{
		if(vis[t.first]) continue;
		minn = 1e9;
		nrt = -1;
		tot = sz[t.first];
		dfs2(t.first, -1);
		csz(nrt, -1);
//		cout << nrt << endl;
		dfs(nrt);
	}
}
struct Line{
	ll k, b;
	ll gt(ll x)
	{
		return x * k + b;
	}
}tr[M << 5];
ll ls[M << 5], rs[M << 5], root[M], num;
void Insert(ll &p, ll l, ll r, Line x)
{
	if(!p)
	{
		tr[p = ++num] = x;
		return;
	}
	if(l == r) return;
	ll mid = (l + r) >> 1ll;
//	cout << "INS: " << x.k << " " << x.b << " " << tr[p].k << " " << tr[p].b << endl;
	if(x.gt(mid) < tr[p].gt(mid)) swap(x, tr[p]);
//	cout << "INS: " << x.k << " " << x.b << " " << tr[p].k << " " << tr[p].b << endl;
	if(x.k < tr[p].k) Insert(rs[p], mid + 1, r, x);// cout << "GTR: " << rs[p] << '\n';
	else Insert(ls[p], l, mid, x);// cout << "GTL: " << p << " " << ls[p] << '\n';
}
ll qry(ll p, ll l, ll r, ll x)
{
	if(!p) return 1e18;
	ll mid = (l + r) >> 1ll;
	ll res = tr[p].gt(x);
//	cout << p << " " << tr[p].k << " " << tr[p].b << " " << res << " " << x << endl;
	if(x <= mid) res = min(res, qry(ls[p], l, mid, x));// cout << "GTL: " << p << " " << ls[p] << '\n';
	else res = min(res, qry(rs[p], mid + 1, r, x));// cout << "GTR: " << rs[p] << '\n';
	return res;
}
void update(int x, Line y)
{
	for(auto t : F[x]) Insert(root[t.first], 0, V, {y.k, y.b + t.second * y.k});// cout << x << " " << t.first << endl;
}
ll query(int x)
{
	ll ans = 1e18;
	for(auto t : F[x]) ans = min(ans, qry(root[t.first], 0, V, t.second));// cout << t.first << " " << x << " " << t.second << " " << qry(root[t.first], 0, V, t.second) << endl;
	return ans;
}
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(ll i = 0; i < n - 1; i++) v[U[i]].push_back({V[i], W[i]}), v[V[i]].push_back({U[i], W[i]});
	csz(0, -1);
	dfs(0);
	vector<int> id(n);
	iota(id.begin(), id.end(), 0);
	sort(id.begin(), id.end(), [&](int x, int y){return B[x] > B[y];});
	for(auto t : id)
	{
		ll ndis = (t == 0 ? 0 : query(t));
//		cout << t << " " << ndis << " " << query(t) << '\n';
		update(t, {B[t], A[t] + ndis});
	}
	vector<ll> res(n - 1);
	for(int i = 1; i < n; i++) res[i - 1] = query(i);
	return res;
}
//signed main()
//{
//	int n;
//	scanf("%d", &n);
//	vector<ll> A;
//	vector<int> B, U, V, W;
//	for(int i = 1, x; i <= n; i++) scanf("%d", &x), A.push_back(x);
//	for(int i = 1, x; i <= n; i++) scanf("%d", &x), B.push_back(x);
//	for(int i = 1, x, y, z; i < n; i++) scanf("%d%d%d", &x, &y, &z), U.push_back(x), V.push_back(y), W.push_back(z);
//	vector<ll> res = travel(A, B, U, V, W);
//	for(int i = 0; i < n - 1; i++) printf("%d ", res[i]);
//	puts("");
//	return 0;
//}