#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
long long n, m, cas, k, cnt, ans;
long long s, tot;
long long dis[maxn], head[maxn];
struct ed {
  long long v, w, next, c;
} e[maxn];
struct edg {
  long long val;
  long long w, sum;
  bool operator<(const edg &b) const { return val < b.val; }
};
void add(long long u, long long v, long long w, long long c) {
  e[cnt].v = v;
  e[cnt].w = w;
  e[cnt].c = c;
  e[cnt].next = head[u];
  head[u] = cnt++;
}
priority_queue<edg> q[3];
void dfs(int u, int fa) {
  dis[u] = 0;
  bool flag = false;
  for (int i = head[u]; i != -1; i = e[i].next) {
    long long v = e[i].v, w = e[i].w, c = e[i].c;
    if (v == fa) continue;
    dfs(v, u);
    flag = true;
    dis[u] += dis[v];
    q[c].push(edg{1ll * (w - (w / 2)) * dis[v], w, dis[v]});
    tot += 1ll * w * dis[v];
  }
  if (!flag) dis[u] = 1;
}
void mainwork() {
  edg x, y, nx, z, nz;
  ans = 0;
  while (tot > s) {
    x.sum = 0;
    y.sum = 0;
    z.sum = 0;
    if (!q[1].empty()) {
      x = q[1].top();
      q[1].pop();
      y.val = 0;
      if (!q[1].empty()) y = q[1].top();
      nx.w = x.w / 2;
      nx.sum = x.sum;
      nx.val = 1ll * (nx.w - (nx.w / 2)) * x.sum;
      if (nx.val > y.val) y = nx;
    }
    if (!q[2].empty()) {
      z = q[2].top(), q[2].pop();
      nz.w = z.w / 2;
      nz.sum = z.sum;
      nz.val = 1ll * (nz.w - (nz.w / 2)) * z.sum;
    }
    if (tot - x.val <= s && x.sum > 0) {
      ++ans;
      return;
    }
    if (x.sum != 0 && z.sum != 0) {
      if (x.val + y.val >= z.val) {
        ans++;
        tot -= x.val;
        q[1].push(nx);
        q[2].push(z);
      } else {
        ans += 2;
        tot -= z.val;
        q[1].push(x);
        q[2].push(nz);
      }
    } else if (x.sum != 0 && z.sum == 0) {
      ans++;
      tot -= x.val;
      q[1].push(nx);
    } else {
      ans += 2;
      tot -= z.val;
      q[2].push(nz);
    }
  }
}
int main() {
  int t = 1;
  scanf("%d", &t);
  for (cas = 1; cas <= t; cas++) {
    scanf("%lld%lld", &n, &s);
    cnt = 0;
    memset(head, -1, sizeof head);
    long long u, v, w, c;
    for (int i = 1; i <= n - 1; i++) {
      scanf("%lld%lld%lld%lld", &u, &v, &w, &c);
      add(u, v, w, c);
      add(v, u, w, c);
    }
    while (!q[1].empty()) q[1].pop();
    while (!q[2].empty()) q[2].pop();
    tot = 0;
    dfs(1, 0);
    mainwork();
    printf("%lld\n", ans);
  }
  return 0;
}
