#include <bits/stdc++.h>
using namespace std;

#define int ll
using ll = long long;
constexpr int inf = 1e18;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector G(n + 1, vector<array<int, 3>>());
    for(int i = 1; i < n; i++) {
        int u, v, l, k;
        cin >> u >> v >> l >> k;
        G[u].push_back({v, l, k});
        G[v].push_back({u, l, k});
    }
    vector<int> c(n + 1), ek(n + 1), el(n + 1), fa(n + 1);
    for(int i = 2; i <= n; i++) {
        cin >> c[i];
    }
    vector f(n + 1, vector(m + 1, 0ll));
    auto merge = [&](vector<int> f, vector<int> g, int l, int r) -> vector<int> {
        vector<int> res(m + 1, inf);
        int i = 0, j = l;
        while(i < m && f[i] == inf) i++;
        while(j < r && g[j] == inf) j++;
        while(i + j <= m) {
            res[i + j] = f[i] + g[j];
            if(j < r && f[i] + g[j + 1] < f[i + 1] + g[j]) j++;
            else i++;
        }
        return res;
    };
    auto dfs = [&](auto self, int x, int fz) -> void {
        fa[x] = fz;
        for(auto [y, l, k] : G[x]) if(y != fz) {
            ek[y] = k, el[y] = l;
            self(self, y, x);
            c[x] = max(c[x], c[y]);
            for(int i = 0; i <= m; i++) {
                f[y][i] += (2 * max(c[y], i) - i) * el[y];
            }
            if(ek[y] < c[y]) {
                f[x] = vector(m + 1, inf);
            } else {
                f[x] = merge(f[x], f[y], max(2 * c[y] - ek[y], 0ll), min(m, ek[y]));
            }
        }
    };
    dfs(dfs, 1, 0);
    // for(int i = 1; i <= n; i++) {
    //     cerr << i << ": ";
    //     for(int j = 0; j <= m; j++) {
    //         cerr << f[i][j] << " \n"[j == m];
    //     }
    // }
    vector<int> ans(m + 1, inf);
    for(int i = 0; i <= m; i++) {
        ans[max(c[1], i)] = min(ans[max(c[1], i)], f[1][i]);
    }
    for(int i = 1; i <= m; i++) {
        if(ans[i] == inf) ans[i] = -1;
        cout << ans[i] << '\n';
    }
    return 0;
}