#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
constexpr ll inf = (1ll<<60);
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)
{
ll N = A.size();
vii edge(N), weight(N);
rep(i,0,N-1){
edge[U[i]].pb(V[i]);
edge[V[i]].pb(U[i]);
weight[U[i]].pb(W[i]);
weight[V[i]].pb(W[i]);
}
vi ans(N,inf);
ans[0] = 0;
std::map<ll,vi> mem;
rep(i,0,N){
mem[-B[i]].pb(i);
}
for(auto el__: mem){
vi v = el__.second;
ll b = -el__.first;
vi dist(N, inf);
std::priority_queue<pii> que;
for(auto el: v){
if(ans[el] == inf) continue;
dist[el] = ans[el]+A[el];
que.push(mp(-dist[el], el));
}
while(!que.empty()){
auto el = que.top(); que.pop();
ll now = el.second;
if(-el.first > dist[now]) continue;
rep(i,0,edge[now].size()){
ll next = edge[now][i];
if(dist[next] > dist[now]+b*weight[now][i]){
dist[next] = dist[now]+b*weight[now][i];
que.push(mp(-dist[next], next));
}
}
}
rep(i,0,N) ans[i] = std::min(ans[i], dist[i]);
}
{
reverse(all(ans));
ans.pop_back();
reverse(all(ans));
}
return ans;
}