#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ll = long long;

#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { x = 0; char GC; bool f = 0;
	for (; !IC; GC) f |= c == '-';
	for (; IC; GC) x = x * 10 + c - 48;
	if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e, v) if (!(e)) { meow("AF@%d\n", __LINE__ ); exit(v); }

#define vc vector
#define eb emplace_back
#define pb push_back

const int N = 10004;
int n, m, c[N], cx[N];

using info = array<ll, N>;
void mkv(info &f, info &g, info &h) {
	h.fill(1e18);
	int i = 0, j = 0, k = 0;
	while (i <= m && f[i] == 1e18) ++i;
	while (j <= m && g[j] == 1e18) ++j;
	if (i > m || j > m)
		return;
	h[i + j] = f[i] + g[j];
	k = i + j + 1;
	++i; ++j;
	for (; i <= m && j <= m && f[i] < 1e18 && g[j] < 1e18 && k <= m; ++k) {
		if (f[i] - f[i - 1] <= g[j] - g[j - 1]) {
			h[k] = h[k - 1] + f[i] - f[i - 1];
			++i;
		} else {
			h[k] = h[k - 1] + g[j] - g[j - 1];
			++j;
		}
	}
	for (; i <= m && f[i] < 1e18 && k <= m; ++i, ++k) {
		h[k] = h[k - 1] + f[i] - f[i - 1];
	}
	for (; j <= m && f[j] < 1e18 && k <= m; ++j, ++k) {
		h[k] = h[k - 1] + g[j] - g[j - 1];
	}
	U (i, 0, m) U (j, 0, m - i) {
		assert(f[i] + g[j] >= h[i + j]);
	}
}

using edge = array<int, 3>;
vc<edge> g[N];
int siz[N], hson[N];
void dfs0(int u, int f) {
	siz[u] = 1; cx[u] = c[u];
	for (auto [v, w, k] : g[u]) if (v != f) {
		dfs0(v, u);
		siz[u] += siz[v];
		cx[u] = max(cx[u], cx[v]);
		if (siz[v] > siz[hson[u]])
			hson[u] = v;
	}
}
void dp(int u, int fa, int fw, int fk, info &f) {
	for (auto [v, w, k] : g[u]) if (v == hson[u]) {
		dp(hson[u], u, w, k, f);
	}
	for (auto [v, w, k] : g[u]) if (v != fa && v != hson[u]) {
		info x {}, y {};
		dp(v, u, w, k, x);
		mkv(f, x, y);
		f = y;
	}
	U (y, 1, m) f[y] = min(f[y], f[y - 1]); // 留在 u
	
	int lb = m + 1, rb = -1;
	U (y, 0, m) {
		int x = max(cx[u], y);
		if (2 * x - y > fk) rb = y;
		else break;
	}
	D (y, m, 0) {
		int x = max(cx[u], y);
		if (2 * x - y > fk) lb = y;
		else break;
	}
	D (i, rb, 0) f[i] = 1e18;
	U (i, lb, m) f[i] = 1e18;
//	U (i, 1, m - 1) {
//		if (f[i] - f[i - 1] > f[i + 1] - f[i])
//			exit(0);
//	}
	
	U (y, 0, m) {
		int x = max(cx[u], y);
		f[y] += (2 * x - y) * fw;
		f[y] = min(f[y], ll(1e18));
	}
}

int main() {
	freopen("ava.in", "r", stdin);
	
	rd(n, m);
	U (i, 2, n) {
		int u, v, w, k; rd(u, v, w, k);
		g[u].pb({v, w, k});
		g[v].pb({u, w, k});
	}
	U (i, 2, n)
		rd(c[i]);
	
	dfs0(1, 0);
	info f {};
	dp(1, 0, 0, 2e9, f);
	info h; h.fill(1e18);
	
	U (y, 0, m) {
		int x = max(cx[1], y);
		h[x] = min(h[x], f[y]);
	}
	U (x, 1, m) {
		h[x] = min(h[x - 1], h[x]);
		if (x < cx[1] || h[x] >= 1e14)
			puts("-1");
		else
			printf("%lld\n", h[x]);
	}
}