#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) {
	U (i, 1, m - 1) {
		assert(f[i] - f[i - 1] <= f[i + 1] - f[i]);
		assert(g[i] - g[i - 1] <= g[i + 1] - g[i]);
	}
	h[0] = f[0] + g[0];
	int i = 1, j = 1, k = 1;
	for (; k <= m; ++k) {
		assert(i <= m);
		assert(j <= m);
		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;
		}
	}
}

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
	U (y, 0, m) {
		int x = max(cx[u], y);
		if (2 * x - y > fk)
			f[y] = (1e4 - y + 1) * 1e14;
	}
	U (y, 0, m) {
		int x = max(cx[u], y);
		f[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 {};
	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]);
	}
}