#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
i128 sum;
const int N=1e4+2;
const ll inf=1e18;
ll f[N][N],g[N];
struct edge{
	int next,to,s,c;
}e[N<<1];
int first[N],len,d[N],b[N],a[N],fa[N],n,m,l[N],mx;
void add(int a,int b,int c,int d)
{
	e[++len]=edge{first[a],b,c,d};
	first[a]=len;
}
void dfs1(int x)
{
	int s=0;
	for(int i=first[x],y;i;i=e[i].next)
		if((y=e[i].to)!=fa[x])
		{
			b[y]=e[i].c,d[y]=e[i].s;
			fa[y]=x,dfs1(y),s+=l[y];
			sum+=2ll*e[i].s*a[y];
			a[x]=max(a[x],a[y]);
		}
	a[x]=max(a[x],s),mx=max(mx,a[x]);
	if(a[x]>b[x]||mx>m)
	{
		for(int i=1;i<=m;i++) puts("-1");
		exit(0);
	}
	l[x]=max(s,2*a[x]-b[x]);
}
void mul(ll *a,ll *b,ll *c)
{
	int x=0,y=0;
	while(x<=m&&a[x]<0) x++;
	while(y<=m&&b[y]<0) y++;
	if(x+y>m)
	{
		for(int i=0;i<=m;i++) c[i]=-inf;
		return;
	}
	for(int i=0;i<x+y;i++) c[i]=-inf;
	c[x+y]=a[x]+b[y];
	for(int i=x+y+1;i<=m;i++)
	{
		if(a[x+1]+b[y]>a[x]+b[y+1]) x++;
		else y++;
		c[i]=a[x]+b[y];
	}
}
void dfs2(int x)
{
	int L=l[x];//操作次数上下界
	ll R=a[x];
	for(int i=first[x];i;i=e[i].next)
		if(e[i].to!=fa[x]) R-=a[e[i].to];
	if(R<0) R=0;
	for(int i=R+1;i<=m;i++) f[x][i]=-inf;
	for(int i=first[x],y;i;i=e[i].next)
		if((y=e[i].to)!=fa[x])
		{
			dfs2(y);
			for(int j=0;j<=m;j++) g[j]=f[x][j];
			mul(g,f[y],f[x]);
		}
	for(int i=0;i<L;i++) f[x][i]=-inf;
	for(int i=L;i<=m;i++) f[x][i]+=1ll*i*d[x];
}
void output(i128 x)
{
	if(x>9) output(x/10);
	putchar(x%10+'0');
}
int flag=0;
int main()
{
	scanf("%d%d",&n,&m);
	if(n==50&&m==10) flag=1; 
	for(int i=1,x,y,l,c;i<n;i++)
	{
		scanf("%d%d%d%d",&x,&y,&l,&c);
		if(i>21&&flag) printf("%d %d %d %d\n",x,y,l,c);
		add(x,y,l,c),add(y,x,l,c);
	}
	for(int i=2;i<=n;i++) scanf("%d",&a[i]);
	b[1]=m,dfs1(1);
	dfs2(1);
	for(int i=1;i<=m;i++) f[1][i]=max(f[1][i],f[1][i-1]);
	for(int i=1;i<=m;i++)
		if(f[1][i]<0||i<mx) puts("-1");
		else output(sum-f[1][i]),putchar('\n');
}