UVA12161 铁人比赛 Ironman Race in Treeland

在树之地里，城镇被无向道路连成了一棵树，就是说，对任意两个城镇，如果你不走重复的一条路，则它们之间都只有恰好一条路径相连。 树之地的国王是个体育迷，所以他想举办一场铁人比赛。赛道是树上的一条简单路径。在比赛期间，社会车辆禁止从赛道经过，所以不可避免地会造成经济损失。更确切的说，每条道路都被算出了一个经济损伤值，而我们的国王希望他的铁人比赛不会过度损伤经济，因此赛道上的所有道路的经济损伤值之和不能超过给定的 $m$。由于我们亲爱的国王是个体育迷，所以我们的道路长度之和必须尽可能大，以让比赛更加精彩。你需要求出这个长度之和的最大值。

第一行包含一个正整数 $T$ 表示测试点个数。 每组数据第一行包含两个正整数 $n,m$，分别表示树的顶点数与经济损失阈值。 接下来 $n-1$ 行，每行四个正整数 $a,b,d,l$，表示从城镇 $a$ 到城镇 $b$ 之间有一条经济损伤值为 $d$ 且长度为 $l$ 的道路。

输出 $T$ 行，每行形如 `Case K: ans`，其中 $K$ 为数据组数，$ans$ 为最长长度之和。

$1 \le T \le 10,1 \le n \le 30000,1 \le m \le 10^8,1 \le a,b \le n,1 \le d,l \le 1000$。保证每组数据都是一棵树。