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

typedef long long ll;

const ll INFLL = 1e18;
const int INF = 0x3f3f3f3f;
const int N = 10005;

struct edge {
	int v, l, k;
	edge (int a = 0, int b = 0, int c = 0) : v(a), l(b), k(c) {}
};

vector <edge> adj[N];
int fa[N], l[N], k[N], c[N];
int n, m;

ll f[N][N], tf[N]; // f[u][i] : cost
int g[N][N], tg[N]; // g[u][i] : u eat i turtles, minimum count of turtle
void dfs1(int u) {
	for (int i = 0; i <= m; i++) g[u][i] = f[u][i] = 0;
	/*
	for (int i = 0; i <= m; i++) {
		g[u][i] = max(0, c[u] - i);
		if (i + g[u][i] > k[u]) {
			g[u][i] = -1;
			continue;
		}
		f[u][i] = 1ll * (i + g[u][i]) * l[u];
	}
	*/
	for (auto t : adj[u]) {
		int v = t.v;
		if (v == fa[u]) continue;
		fa[v] = u; l[v] = t.l; k[v] = t.k; dfs1(v);
		memset(tg, 0x3f, sizeof(tg));
		for (int i = 0; i <= n; i++) {
			if (g[u][i] == INF) continue;
			for (int j = 0; j <= n - i; j++) {
				if (g[v][j] == INF) continue;
				int ng = max(g[u][i], j + g[v][j]);
				if (ng < tg[i + j]) {
					tf[i + j] = f[u][i] + f[v][j];
					tg[i + j] = ng;
				} else if (ng == tg[i + j]) {
					tf[i + j] = min(tf[i + j], f[u][i] + f[v][j]);
				}
			}
		}
		memcpy(f[u], tf, sizeof(f[u]));
		memcpy(g[u], tg, sizeof(g[u]));
	}
	for (int i = 0; i <= m; i++) {
		if (g[u][i] == INF) continue;
		g[u][i] = max(0, g[u][i] - i);
		g[u][i] = max(g[u][i], c[u] - i);
	}
	for (int i = 0; i < m; i++) {
		if (g[u][i] == INF) continue;
		if (max(0, g[u][i] - 1) < g[u][i + 1]) {
			g[u][i + 1] = g[u][i] - 1;
			f[u][i + 1] = f[u][i];
		} else if (max(0, g[u][i] - 1) == g[u][i + 1]) {
			f[u][i + 1] = min(f[u][i + 1], f[u][i]);
		}
	}
	for (int i = 0; i <= m; i++) {
		if (i + g[u][i] * 2 > k[u]) {
			g[u][i] = INF;
		}
		if (g[u][i] != INF) f[u][i] += 1ll * l[u] * (i + g[u][i] * 2);
	}
}

ll ans[N];

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int u, v, l, k;
		cin >> u >> v >> l >> k;
		adj[u].emplace_back(v, l, k);
		adj[v].emplace_back(u, l, k);
	}
	k[1] = 1e9;
	for (int i = 2; i <= n; i++) cin >> c[i];
	dfs1(1);
	for (int i = 0; i <= m; i++) ans[i] = INFLL;
	for (int i = 0; i <= m; i++) {
		if (g[1][i] != INF) {
			ans[i + g[1][i]] = min(ans[i + g[1][i]], f[1][i]);
		}
	}
	for (int i = 1; i <= m; i++) ans[i] = min(ans[i], ans[i - 1]);
	for (int i = 1; i <= m; i++) {
		if (ans[i] == INFLL) cout << -1 << '\n';
		else cout << ans[i] << '\n';
	}
	return 0;
}