#include <bits/stdc++.h>
#include <iostream>
#include <set>
#include <string>
#include <map>
using namespace std;

typedef long long ll;
#define pb push_back
#define SZ 333333
int m,n;
vector<int> ee[SZ];
int eab[SZ],l[SZ],k[SZ];
int c[SZ];
ll fl[SZ],fk[SZ];
void dfs(int x,int fa=-1) {
    for(auto e:ee[x]) {
        int b=eab[e]^x;
        if(b==fa) continue;
        fl[b]=l[x]; fk[b]=k[x];
        dfs(b,x);
        c[x]=max(c[x],c[b]);
    }
}
int cap[SZ],lb[SZ];
ll t[10005][10005];
ll INF;
ll s[50005];
void mg(ll*a,ll*b,int u1,int u2,int uup) {
    for(int i=0;i<=uup;++i) s[i]=-INF;
    for(int i=0;i<=u1;++i)
        for(int j=0;j<=u2&&i+j<=uup;++j)
            if(a[i]>=0&&b[j]>=0)
            s[i+j]=max(s[i+j],a[i]+b[j]);
    for(int i=0;i<=uup;++i) a[i]=s[i];
}
void dp(int x,int fa=-1) {
    int up=0;
    t[x][0]=0;
    for(auto e:ee[x]) {
        int b=eab[e]^x;
        if(b==fa) continue;
        dp(b,x);
        int uup=min(up+cap[b],cap[x]);
        mg(t[x],t[b],up,cap[b],uup);
        up=uup;
    }
    for(int i=0;i<=m;++i) t[x][i]+=1LL*i*fl[x];
    for(int i=0;i<=lb[i];++i) t[x][i]=-INF;
    cap[x]=min(cap[x],up);
}
int main() {
    memset(t,-127/3,sizeof t);
    INF=-t[0][0];
    scanf("%d%d",&n,&m);
    cerr<<"++"<<m<<"\n";
    for(int i=1;i<n;++i) {
        int a,b;
        scanf("%d%d%d%d",&a,&b,l+i,k+i);
        eab[i]=a^b;
        ee[a].pb(i);
        ee[b].pb(i);
    }
    for(int i=2;i<=n;++i)
        scanf("%d",c+i);
    dfs(1);
    ll g=0;
    for(int i=2;i<=n;++i) {
        g+=c[i]*fl[i]*2;
        // cap c[i], lb 2c[i]-k[i]
        int cap=min(c[i],m),lb=max(2*c[i]-(int)fk[i],0);
        if(lb>cap) {
            while(m--)
                cout<<"-1\n";
            return 0;
        }
        ::cap[i]=cap;
        ::lb[i]=lb;
        cout<<i<<": "<<cap<<"  "<<lb<<"\n";
    }
    cap[1]=m; lb[1]=0;
    cout<<"GG"<<g<<"\n";
    dp(1);
    cerr<<"SSS"<<cap[1]<<"\n";
    for(int i=0;i<=cap[1];++i)
        cout<<t[1][i]<<",";
    cout<<"\n";
}