#include <vector>
#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()

using i64 = long long;

struct Edge {
    int to;
    i64 cost;
};

struct CHTMonotone {
    using P = pair<i64, i64>;
    deque<P> deq;

    i64 eval(const P &line, i64 x) {
        return line.first * x + line.second;
    }

    bool check(const P &l1, const P &l2, const P &l3) {
        __int128_t a = (__int128_t)(l3.second - l2.second) * (l2.first - l1.first);
        __int128_t b = (__int128_t)(l2.second - l1.second) * (l3.first - l2.first);
        return a >= b;
    }

    // add decreasing
    // query decreasing
    void add(const P &line) {
        if (deq.empty()) deq.push_front(line);
        else {
            if (deq.front().first == line.first) {
                if (deq.front().second > line.second) {
                    deq.pop_front();
                } else {
                    return;
                }
            }
            while (deq.size() >= 2 and check(line, deq[0], deq[1])) deq.pop_front();
            deq.push_front(line);
        }
    }

    i64 query(i64 x) {
        if (deq.empty()) return 1ll << 60;
        i64 mi = 1ll << 60;
        for (const auto &line : deq) mi = min(mi, eval(line, x));
        return mi;
    }
};

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)
{
    const int N = (int)A.size(), M = (int)U.size();
    vector<vector<Edge>> tree(N);
    rep(i, 0, M) {
        tree[U[i]].push_back({V[i], W[i]});
        tree[V[i]].push_back({U[i], W[i]});
    }

    vector<int> par(N);
    vector<i64> depth(N);
    vector<int> dep1(N);
    auto dfs = [&](auto &&self, const int v, const int p, i64 d, int d1) -> void {
        par[v] = p;
        depth[v] = d;
        dep1[v] = d1;
        for (const auto &[t, c] : tree[v]) {
            if (t == p) continue;
            self(self, t, v, d + c, d1 + 1);
        }
    };
    dfs(dfs, 0, -1, 0, 0);

    vector<vector<int>> table(20, vector<int>(N));
    table[0] = par;
    rep(rank, 1, 20) {
        rep(i, 0, N) {
            if (table[rank - 1][i] == -1) table[rank][i] = -1;
            else table[rank][i] = table[rank - 1][table[rank - 1][i]];
        }
    }

    auto calcLCA = [&](int u, int v) {
        if (dep1[u] > dep1[v]) swap(u, v);
        per(rank, 0, 20) {
            const int t = table[rank][v];
            if (t != -1 and dep1[t] >= dep1[u]) {
                v = t;
            }
        }
        if (u == v) return u;
        per(rank, 0, 20) {
            const int a = table[rank][u], b = table[rank][v];
            if (a == b) continue;
            u = a, v = b;
        }
        return par[u];
    };

    auto calcDist = [&](int a, int b) {
        const auto lca = calcLCA(a, b);
        return depth[a] + depth[b] - 2 * depth[lca];
    };

    vector<CHTMonotone> chts(N);
    vector<vector<int>> roots(N);

    vector<bool> isAvailable(N, true);
    vector<int> subSize(N);

    auto centDec = [&](auto &&self, const int root) -> void {
        auto dfs1 = [&](auto &&self, const int v, const int p) -> int {
            subSize[v] = 1;
            for (const auto &[t, c] : tree[v]) {
                if (t == p) continue;
                if (not isAvailable[t]) continue;
                subSize[v] += self(self, t, v);
            }
            return subSize[v];
        };
        dfs1(dfs1, root, -1);

        int centroid = -1, sSum = subSize[root];
        auto dfs2 = [&](auto &&self, const int v, const int p) -> void {
            bool isCen = true;
            for (const auto &[t, c] : tree[v]) {
                if (t == p) continue;
                if (not isAvailable[t]) continue;
                self(self, t, v);
                if (subSize[t] > sSum / 2) isCen = false;
            }
            if (sSum - subSize[v] > sSum / 2) isCen = false;
            if (isCen) centroid = v;
        };
        dfs2(dfs2, root, -1);

        auto dfs3 = [&](auto &&self, const int v, const int p) -> void {
            roots[v].push_back(centroid);
            for (const auto &[t, c] : tree[v]) {
                if (t == p) continue;
                if (not isAvailable[t]) continue;
                self(self, t, v);
            }
        };
        dfs3(dfs3, root, root);

        for (const auto &[t, c] : tree[centroid]) {
            if (not isAvailable[t]) continue;
            subSize[t] = -centroid - 1;
            isAvailable[t] = false;
        }
        isAvailable[centroid] = false;

        for (const auto &[t, c] : tree[centroid]) {
            if (subSize[t] == -centroid - 1) {
                subSize[t] = 0;
                isAvailable[t] = true;
            }
            if (not isAvailable[t]) continue;
            self(self, t);
            isAvailable[t] = false;
        }
    };
    centDec(centDec, 0);

    vector<pair<i64, int>> vs;
    rep(i, 0, N) vs.push_back({B[i], i});
    sort(ALL(vs), greater());
    vector<i64> dist(N, 1ll << 60);
    dist[0] = 0;
    for (const auto &[b, i] : vs) {
        for (const auto r : roots[i]) {
            i64 d = calcDist(i, r);
            i64 cost = chts[r].query(d);
            dist[i] = min(dist[i], cost);
        }

        if (dist[i] == (1ll << 60)) continue;
        const auto baseCost = dist[i] + A[i];
        for (const auto r : roots[i]) {
            i64 d = calcDist(i, r);
            i64 cost = d * B[i];
            chts[r].add({B[i], baseCost + cost});
        }
    }

    vector<i64> ans(N - 1);
    rep(i, 1, N) {
        for (const auto r : roots[i]) {
            i64 d = calcDist(i, r);
            i64 cost = chts[r].query(d);
            dist[i] = min(dist[i], cost);
        }
        ans[i - 1] = dist[i];
    }
    return ans;
}