#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,m;
int a[10005];

int cnt;
int head[10005];
struct eg{
	int to,nxt,w,k;
}edge[20005];

void make(int u,int v,int w,int k){
	edge[++cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].k = k;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

ll ssum;
int fa[10005],_l[10005],_r[10005],_val[10005],sum[10005];
void dfs(int u,int f){
	fa[u] = f;
	for(int i = head[u];i;i = edge[i].nxt){
		int v = edge[i].to;
		if(v == f) continue;
		dfs(v,u);
		_val[v] = edge[i].w;
		ssum += 2ll * _val[v] * a[v];
		_l[v] = 2 * a[v] - edge[i].k;
		_r[v] = a[v];
		sum[u] += a[v];
	}
	chkmax(a[u],sum[u]);
}

ll dp[1005][1005],temp[1005];
void dfs2(int u){
	fill(dp[u],dp[u] + m + 1,-linf);
	dp[u][0] = 0;
	for(int i = head[u];i;i = edge[i].nxt){
		int v = edge[i].to;
		if(v == fa[u]) continue;
		dfs2(v);
		fill(temp,temp + m + 1,-linf);
		rep(j,0,m){
			rep(k,0,m - j) chkmax(temp[j + k],dp[u][j] + dp[v][k]);
		}
		copy(temp,temp + m + 1,dp[u]);
	}
/*	printf("node %d\n",u);	
	rep(i,0,m) printf("%lld ",dp[u][i]);
	printf("\n");*/
	rep(i,1,m) chkmax(dp[u][i],dp[u][i - 1]);
	rep(i,0,m){
		dp[u][i] += 1ll * i * _val[u];
		if(i < _l[u] || i > _r[u]) dp[u][i] = -linf;
	}
//	rep(i,0,m) printf("%lld ",dp[u][i]);
//	printf("\n");
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d%d",&n,&m);
	rep(i,1,n - 1){
		int u,v,w,k;
		scanf("%d%d%d%d",&u,&v,&w,&k);
		make(u,v,w,k);make(v,u,w,k);
	}
	rep(u,2,n) scanf("%d",&a[u]);
	dfs(1,0);
	_l[1] = 0;_r[1] = m;
//	rep(u,1,n) printf("%d ",a[u]);
//	printf("\n");
//	rep(u,1,n) printf("[%d,%d]\n",_l[u],_r[u]);
	dfs2(1);
	rep(i,1,m){
		chkmax(dp[1][i],dp[1][i - 1]);
		if(dp[1][i] == -linf || i < sum[1]) printf("-1\n");
		else printf("%lld\n",ssum - dp[1][i]);
	}
	return 0;
}