#include<bits/stdc++.h>

using namespace std;

const int maxn = 3e4+;

int n,m;

int hd[maxn], nx[maxn<<], to[maxn<<], dam[maxn<<], len[maxn<<], ec;

inline void add(int u,int v,int D,int L)

{

    to[ec] = v;

    dam[ec] = D;

    len[ec] = L;

    nx[ec] = hd[u];

    hd[u] = ec++;

}

int root, best;

int ct[maxn];

//best = n

void GetBaryCenter(int u,int f)

{

    ct[u] = ;

    int Mx = ;

    for(int i = hd[u]; ~i; i = nx[i]){

        if(to[i] != f){

            GetBaryCenter(to[i], u);

            ct[u] += ct[to[i]];

            Mx = max(Mx,ct[to[i]]);

        }

    }

    Mx = max(Mx,n-ct[u]);

    if(Mx < best){

        best = Mx;

        root = u;

    }

}

#define MP make_pair

#define fi first

#define se second

int C[maxn], L[maxn];

map<int,int> mp;

map<int,int>::iterator it;

int ans;

int path[maxn];

int pre[maxn], dfs_clk;

//dfs_clk = 0, ans = 0;

void dfs(int u = root,int f = )

{

    path[dfs_clk] = u;

    pre[u] = dfs_clk++;

    C[u] = ; L[u] = ;

    for(int i = hd[u]; ~i; i = nx[i]){

        if(to[i] != f){

            int v = to[i];

            dfs(v,u);

            for(int j = pre[v]; j < dfs_clk ; j++){

                int x = path[j];

                C[x] += dam[i];

                L[x] += len[i];

            }

        }

    }

    //子树都访问完里以后统一处理以保证互不干扰，这样mp就可以设置为全局变量

    mp.clear();

    for(int i = hd[u]; ~i; i = nx[i]){

        int nex = nx[i];

        int lim = ~nex? pre[to[nex]] : dfs_clk;

        if(to[i] != f){

            int v = to[i];

            for(int j = pre[v]; j < lim ; j++){

                int x = path[j];

                if(C[x] <= m){

                    ans = max(ans,L[x]);

                    it = mp.upper_bound(m-C[x]);//找到一个key <= C[x]

                    if(it != mp.begin()){

                        ans = max(ans,(--it)->second+L[x]);

                    }

                }

            }

            for(int j = pre[v]; j < lim ; j++){

                int x = path[j];

                if(C[x] <= m){

                    it = mp.lower_bound(C[x]);

                    bool swc = false;

                    if(it == mp.begin() || (swc = true , L[x] > (--it)->se) ){

                        if(swc) it++;

                        while(it != mp.end() && it->se <= L[x]) mp.erase(it++);

                        if(it == mp.end() || it->fi > C[x]) {//lower_bound可能使得it指向key == C[x] 而 val >= L[x]

                            mp.insert(MP(C[x],L[x]));

                        }

                    }

                }

            }

        }

    }

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int T, ks = ; cin>>T;

    while(T--){

        scanf("%d%d",&n,&m);

        memset(hd+,-,sizeof(int)*n); ec = ;

        for(int i = n; --i;){

            int a,b,D,L; scanf("%d%d%d%d",&a,&b,&D,&L);

            add(a,b,D,L); add(b,a,D,L);

        }

        best = n+;

        GetBaryCenter(,);

        dfs_clk = ans = ;

        dfs();

        printf("Case %d: %d\n",++ks,ans);

    }

    return ;

}