#include <bits/stdc++.h>
using std::multiset;
const int maxn = 1e5 + 1;
inline long long max(long long a, long long b) { return a > b ? a : b; }
inline long long min(long long a, long long b) { return a < b ? a : b; }
struct Edge {
  long long u, v, w, c;
  inline void clear() {
    u = 0;
    v = 0;
    w = 0;
    c = 0;
  }
} e[maxn << 1];
long long head[maxn], ecnt;
inline void addedge(long long u, long long v, long long w, long long c) {
  e[++ecnt].v = v;
  e[ecnt].w = w;
  e[ecnt].c = c;
  e[ecnt].u = head[u];
  head[u] = ecnt;
}
inline void add(long long u, long long v, long long w, long long c) {
  addedge(u, v, w, c);
  addedge(v, u, w, c);
}
long long siz[maxn], val, son[maxn], F[maxn], n, S, a, b, c, d, sum, ch1, ch2,
    ch3, cha, Ans, cnt1, cnt2, ans1[maxn << 5], ans2[maxn << 5], n1, n2, pos1,
    pos2;
inline void dfs(long long x, long long f) {
  son[x] = 1;
  for (long long i = head[x], v; i; i = e[i].u) {
    v = e[i].v;
    if (v == f) {
      F[x] = i;
      continue;
    }
    son[x]++;
  }
  if (son[x] == 1)
    siz[x] = 1;
  else
    siz[x] = 0;
  for (long long i = head[x], v; i; i = e[i].u) {
    v = e[i].v;
    if (v == f) continue;
    dfs(v, x);
    siz[x] += siz[v];
  }
}
struct Node {
  long long siz, val, delta;
  inline bool operator<(Node nmd) const { return nmd.delta < delta; }
} t1, t2, t3;
multiset<Node> q1, q2;
inline long long get(long long A, long long B) { return (A * ((B + 1) >> 1)); }
inline void solve() {
  scanf("%lld %lld", &n, &S);
  for (long long i = 1; i <= ecnt; i++) e[i].clear();
  ecnt = 0;
  for (long long i = 1; i <= n; i++) head[i] = 0, F[i] = 0;
  sum = 0;
  q1.clear();
  q2.clear();
  for (long long i = 1; i <= n - 1; i++)
    scanf("%lld %lld %lld %lld", &a, &b, &c, &d), add(a, b, c, d);
  dfs(1, 0);
  for (long long i = 2; i <= n; i++) sum += (siz[i] * e[F[i]].w);
  if (sum <= S) return (void)(puts("0"));
  cha = (sum - S);
  ch1 = 0;
  ch2 = 0;
  for (long long i = 2; i <= n; i++) {
    if (e[F[i]].c == 1)
      q1.insert((Node){siz[i], e[F[i]].w, get(siz[i], e[F[i]].w)});
    else
      q2.insert((Node){siz[i], e[F[i]].w, get(siz[i], e[F[i]].w)});
  }
  Ans = 0x3f3f3f3f;
  n1 = 0;
  n2 = 0;
  while (ch1 <= cha) {
    if (q1.empty()) break;
    t1 = (*q1.begin());
    q1.erase(q1.begin());
    ch3 = t1.delta;
    ch1 += ch3;
    ans1[++n1] = ch1;
    if (t1.val > 1)
      q1.insert((Node){t1.siz, t1.val >> 1, get(t1.siz, t1.val >> 1)});
  }
  while (ch2 <= cha) {
    if (q2.empty()) break;
    t2 = (*q2.begin());
    q2.erase(q2.begin());
    ch3 = t2.delta;
    ch2 += ch3;
    ans2[++n2] = ch2;
    if (t2.val > 1)
      q2.insert((Node){t2.siz, t2.val >> 1, get(t2.siz, t2.val >> 1)});
  }
  pos1 = n1;
  pos2 = 0;
  while (pos1 >= 0) {
    while ((ans1[pos1] + ans2[pos2] < cha) && pos2 <= n2) pos2++;
    if (pos2 > n2) break;
    Ans = min(Ans, pos1 + pos2 * 2);
    pos1--;
  }
  printf("%lld\n", Ans);
}
signed main() {
  long long TEST;
  scanf("%lld", &TEST);
  while (TEST--) solve();
}
