#include <bits/stdc++.h>

using LL = long long;

constexpr int inf32 = (int)(1e9) + 9;
constexpr LL inf64 = (LL)(1e18) + 18;

constexpr int N = 10004;

int n, m, c[N];
std::vector<std::tuple<int, int, int>> tree[N];
struct Vec2 : std::pair<int, LL> { using std::pair<int, LL>::pair; };
Vec2 operator+(Vec2 a, Vec2 b) { return {a.first + b.first, a.second + b.second}; }
Vec2 operator-(Vec2 a, Vec2 b) { return {a.first - b.first, a.second - b.second}; }
__int128 cross(Vec2 a, Vec2 b) { return __int128(a.first) * b.second - __int128(a.second) * b.first; }
std::vector<Vec2> h[N];
std::vector<Vec2> merge(std::vector<Vec2> a, std::vector<Vec2> b) {
    if (!a.size() || !b.size()) return {};
    std::vector<Vec2> res = {a[0] + b[0]};
    for (int i = 1, j = 1; i < a.size() || j < b.size(); ) {
        if (i == a.size()) {
            res.push_back(res.back() + b[j] - b[j - 1]);
            j++;
            continue;
        }
        if (j == b.size()) {
            res.push_back(res.back() + a[i] - a[i - 1]);
            i++;
            continue;
        }
        auto x = a[i] - a[i - 1], y = b[j] - b[j - 1];
        if (cross(x, y) > 0) {
            res.push_back(res.back() + a[i] - a[i - 1]);
            i++;
        }
        else {
            res.push_back(res.back() + b[j] - b[j - 1]);
            j++;
        }
    }
    return res;
}

void dfs(int u, int p) {
    int t = 0;
    h[u].resize(m + 1);
    for (int i = 0; i <= m; i++) h[u][i] = {i, 0};
    for (auto [v, l, k] : tree[u]) {
        if (v == p) continue;
        dfs(v, u);
        std::vector<Vec2> _h;
        for (auto [x, y] : h[v]) {
            int w = 2 * std::max(c[v], x) - x;
            if (w <= k) _h.push_back({x, y + 1ll * l * w});
        }
        std::swap(h[u], _h);
        h[u] = merge(h[u], h[v]);
        c[u] = std::max(c[u], c[v]);
    }
}

LL ans[N];

int main() {
    std::cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int x, y, l, k;
        std::cin >> x >> y >> l >> k;
        tree[x].push_back({y, l, k});
        tree[y].push_back({x, l, k});
    }
    for (int i = 2; i <= n; i++) std::cin >> c[i];
    dfs(1, 0);
    std::fill_n(ans, m + 1, -1);
    for (auto [x, y] : h[1]) if (x >= c[1]) ans[x] = y;
    for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
    return 0;
}