#include <bits/stdc++.h>
#define ll long long
#define N 10011
using namespace std;
int n,M,c[N];ll g[N][N],ng[N];
struct edge{int v,l,k;};
vector<edge> G[N];
const ll inf=1e18;
void minkow(ll *f,ll *g,ll *h)
{
	int hpt=0,fpt=0,gpt=0;
	while(fpt+gpt<M&&g[gpt]>=inf)++gpt;
	for(int i=0;i<fpt+gpt;++i)h[i]=inf;
	h[fpt+gpt]=min(f[fpt]+g[gpt],inf);
	for(int i=fpt+gpt+1;i<=M;++i)
	{
		ll vf=inf;
		if(f[fpt+1]<inf)vf=f[fpt+1]-f[fpt];
		ll vg=inf;
		if(g[gpt+1]<inf)vg=g[gpt+1]-g[gpt];
		if(min(vf,vg)>=inf){for(int j=i;j<=M;++j)h[j]=inf;break;}
		if(vf<vg)++fpt;else ++gpt;
		h[i]=f[fpt]+g[gpt];
	}
}
void dfs(int u,int F,int fal,int fak)
{
	for(auto [v,l,k]:G[u])if(v^F)dfs(v,u,l,k),c[u]=max(c[u],c[v]);
	g[u][0]=0;
	for(auto [v,l,k]:G[u])if(v^F)
	{
		minkow(g[u],g[v],ng);
		for(int i=0;i<=M;++i)g[u][i]=ng[i];
	}
	for(int i=1;i<=M;++i)g[u][i]=min(g[u][i],g[u][i-1]);
	for(int i=0;i<=M;++i)
	{
		int f=max(c[u],i);
		if((fak+i)/2<f){g[u][i]=inf;continue;}
		g[u][i]+=1ll*(2*f-i)*fal;
	}
}
int main()
{
	scanf("%d%d",&n,&M);
	memset(g,0x3f,sizeof(g));
	for(int i=1;i<n;++i){int u,v,l,k;scanf("%d%d%d%d",&u,&v,&l,&k);G[u].push_back({v,l,k});G[v].push_back({u,l,k});}
	for(int i=2;i<=n;++i)scanf("%d",c+i);
	dfs(1,0,0,M);
	for(int i=1;i<=M;++i)
	{
		if(g[1][i]>=inf||i<c[1])printf("-1\n");else printf("%lld\n",g[1][i]);
	}
}