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

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

ll dis[MAXN][MAXN];

void dfs_dis(int u,int fa,int rt)
{
	for(auto it: g[u]) if(it.first != fa)
	{
		dis[rt][it.first] = dis[rt][u] + it.second;
		dfs_dis(it.first, u, rt);
	}
}

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

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);
	}
	
	for(int i=1; i<=n; ++i)
		dfs_dis(i, 0, i);
	
	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 v=1; v<=n; ++v)
		{
			ll cur = f[u] + a[u] + b[u] * dis[u][v];
			if(cur < f[v])
			{
				f[v] = cur;
				q.emplace(-f[v], v);
			}
		}
	}
	
	return vector<ll>(f+2, f+n+1);
}