#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;
const ll inf = 4e18;
int n, m, c[N], cx[N];

struct info {
	int l, r;
	array<ll, N> v;
};
void mkv(info &f, info &g, info &h) {
	h.v.fill(inf); h.l = min(m + 1, f.l + g.l); h.r = min(m, f.r + g.r);
	
	U (i, f.l, f.r) U (j, g.l, g.r) if (i + j <= m)
		h.v[i + j] = min(h.v[i + j], f.v[i] + g.v[j]);
	U (i, h.l + 1, h.r - 1) {
		assert(h.v[i] - h.v[i - 1] <= h.v[i + 1] - h.v[i]);
	}
}

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 {};
		x.l = 0, x.r = m;
		
		dp(v, u, w, k, x);
		mkv(f, x, y);
		f = y;
	}
	U (y, f.l + 1, m) {
		if (y <= f.r)
			f.v[y] = min(f.v[y], f.v[y - 1]); // 留在 u
		else
			f.v[y] = f.v[y - 1];
	}
	
	int lb = m + 1, rb = f.l - 1;
	U (y, f.l, m) {
		int x = max(cx[u], y);
		if (2 * x - y > fk) rb = y;
		else break;
	}
	D (y, m, f.l) {
		int x = max(cx[u], y);
		if (2 * x - y > fk) lb = y;
		else break;
	}
	if (rb < lb) {
		assert(rb + 1 < lb);
		f.l = rb + 1;
		f.r = lb - 1;
	} else {
		f.l = m + 1, f.r = m;
	}
	
	U (y, f.l, f.r) {
		int x = max(cx[u], y);
		f.v[y] += (2 * x - y) * fw;
	}
}

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 {}; f.l = 0, f.r = m;
	dp(1, 0, 0, 2e9, f);
	array<ll, N> h; h.fill(inf);
	
	U (y, f.l, f.r) {
		int x = max(cx[1], y);
		h[x] = min(h[x], f.v[y]);
	}
	U (x, 1, m) {
		h[x] = min(h[x - 1], h[x]);
		if (x < cx[1] || h[x] >= inf)
			puts("-1");
		else
			printf("%lld\n", h[x]);
	}
}