#include <bits/stdc++.h>
#define mp make_pair
#define y e[x][i].vv
#define w e[x][i].cc
#define l e[x][i].ww
using namespace std;
typedef map<int,int>::iterator MI;
const int N=30005;
int t,tot,n,m,rt,s,ans,sz[N],ss[N];
bool vis[N];
struct edge{int vv,cc,ww;};
vector<edge> e[N];
void getrt(int x,int fa){
	ss[x]=0;
	for(int i=0;i<e[x].size();i++)
		if(y!=fa&&!vis[y]) {getrt(y,x);ss[x]=max(ss[x],sz[y]);}
	if((ss[x]=max(ss[x],s-sz[x]))<ss[rt]) rt=x;
}
void ins(map<int,int>&d,int p,int q){
	MI it=d.upper_bound(p);
	if((--it)->second<q){
		d[p]=q;it=d.upper_bound(p);
		while(it!=d.end()&&it->second<=q) d.erase(it++); 
	}
}
void getd(int x,int fa,int len,int val,map<int,int>&p){
	sz[x]=1;p[len]=val;
	for(int i=0;i<e[x].size();i++)
		if(y!=fa&&!vis[y]) {getd(y,x,len+w,val+l,p);sz[x]+=sz[y];}
}
int dfs(int x){
	vis[x]=1;map<int,int> d,p;d.clear();d[0]=0;
	for(int i=0;i<e[x].size();i++)
		if(!vis[y]){
			p.clear();getd(y,x,w,l,p);
			for(MI it=p.begin();it!=p.end();it++){
				MI now=d.upper_bound(m-it->first);
				if(now!=d.begin()) ans=max(ans,it->second+(--now)->second);
			}
			for(MI it=p.begin();it!=p.end();it++) ins(d,it->first,it->second);
		}
	for(int i=0;i<e[x].size();i++)
		if(!vis[y]) {ss[rt=0]=s=sz[y];getrt(y,x);dfs(rt);}
}
void solve(){
	scanf("%d%d",&n,&m);ans=0;
    for(int i=1;i<=n;i++) {e[i].clear();vis[i]=0;sz[i]=1;}
	for(int i=1,u,v,c,x;i<n;i++) {scanf("%d%d%d%d",&u,&v,&c,&x);e[u].push_back((edge){v,c,x});e[v].push_back((edge){u,c,x});}
	ss[rt]=s=n;getrt(1,0);dfs(rt);printf("Case %d: %d\n",++tot,ans);
}
signed main(){
	scanf("%d",&t);while(t--) solve();
	return 0;
}

爆栈什么的试过了，都改了14514次还是RE（难道要改19191810次吗）