#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define eb emplace_back
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;

template<class T> inline T& cmin(T& a, const T& b) { if(b < a) a = b; return a; }
template<class T> inline T& cmax(T& a, const T& b) { if(a < b) a = b; return a; }
template<class... Args> void print(Args&&... args) {
#ifdef local
    ((cout << args << ' '), ...);
#endif
}
template<class... Args> void println(Args&&... args) {
#ifdef local
    print(args...), cout << endl;
#endif
}

const int N = 1e5 + 8;

ll a[N], ans[N];
int b[N];
vector<pair<int, int>> G[N];

struct Line {
    ll k, b;
    ll operator () (ll x)const {
        return k * x + b;
    }
};
int idx;
struct {
    int l, r;
    Line x;
} c[N * 40];

int insert(Line x, ll l, ll r, int o) {
    int oo = ++idx;
    c[oo] = c[o];
    ll m = (l + r) >> 1;
    if(x(m) < c[oo].x(m)) swap(x, c[oo].x);
    if(l == r) return oo;
    if(x(l) < c[oo].x(l)) c[oo].l = insert(x, l, m, c[oo].l);
    if(x(r) < c[oo].x(r)) c[oo].r = insert(x, m + 1, r, c[oo].r);
    return oo;
}
ll query(ll i, ll l, ll r, int o) {
    ll res = 1e18;
    while(o) {
        cmin(res, c[o].x(i));
        ll m = (l + r) >> 1;
        tie(l, r, o) = i <= m ? tuple(l, m, c[o].l) : tuple(m + 1, r, c[o].r);
    }
    return res;
}
void dfs(int u, int f, int o, ll dep) {
    if(u) ans[u] = query(dep, 0, 1e11, o);
    o = insert({b[u], ans[u] + a[u] - dep * b[u]}, 0, 1e11, o);
    for(auto [v, w] : G[u]) if(v != f)
        dfs(v, u, o, dep + w);
}
vector<ll> travel(vector<ll> A, vector<int> B, vector<int> U, vector<int> V, vector<int> W) {
    For(i, 0, SZ(A)) a[i] = A[i], b[i] = B[i];
    For(i, 0, SZ(U)) G[U[i]].eb(V[i], W[i]), G[V[i]].eb(U[i], W[i]);
    c[0].x = {0, (ll)1e18};
    dfs(0, 0, 0, 0);
    return vector(ans + 1, ans + SZ(A));
}