#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int h[maxn], ee = 1;
struct Edge {
  int v, w, c, next;
} e[maxn * 2];
struct Node {
  int id, cnt;
  long long val;
  bool operator<(const Node a) const { return val < a.val; }
};
priority_queue<Node> q1, q2;
int sz[maxn], a[maxn * 2], tot = 0;
void addedge(int u, int v, int w, int c) {
  e[ee] = Edge{v, w, c, h[u]};
  h[u] = ee++;
}
long long now = 0;
void dfs(int u, int f) {
  sz[u] = 1;
  bool fg = false;
  for (register int i = h[u]; i; i = e[i].next) {
    int v = e[i].v, w = e[i].w, c = e[i].c;
    if (v == f) continue;
    fg = true;
    dfs(v, u);
    if (c == 1) {
      ++tot;
      a[tot] = w;
      q1.push(Node{tot, sz[v], 1ll * sz[v] * (a[tot] - a[tot] / 2)});
      a[tot] /= 2;
      q1.push(Node{tot, sz[v], 1ll * sz[v] * (a[tot] - a[tot] / 2)});
      a[tot] /= 2;
    } else {
      ++tot;
      a[tot] = w;
      q2.push(Node{tot, sz[v], 1ll * sz[v] * (a[tot] - a[tot] / 2)});
      a[tot] /= 2;
    }
    now += 1ll * w * sz[v];
    sz[u] += sz[v];
  }
  sz[u] -= fg;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    long long s;
    ee = 1;
    tot = 0;
    scanf("%d%lld", &n, &s);
    for (int i = 1; i <= n; ++i) h[i] = 0;
    for (int i = 0; i < n - 1; ++i) {
      int u, v, w, c;
      scanf("%d%d%d%d", &u, &v, &w, &c);
      addedge(u, v, w, c);
      addedge(v, u, w, c);
    }
    now = 0;
    dfs(1, 0);
    int ans = 0;
    bool fg1 = !q1.empty(), fg2 = !q2.empty();
    while (now > s) {
      Node u11, u12;
      if (fg1) {
        u11 = q1.top();
        q1.pop();
        u12 = q1.top();
        q1.pop();
      }
      Node u2;
      if (fg2) {
        u2 = q2.top();
        q2.pop();
      }
      if (fg1 && fg2) {
        if (u2.val >= u11.val + u12.val) {
          if (now - u11.val <= s) {
            ans++;
            break;
          }
          now -= u2.val;
          ans += 2;
          u2.val = 1ll * u2.cnt * (a[u2.id] - a[u2.id] / 2);
          a[u2.id] /= 2;
        } else {
          now -= u11.val;
          ans++;
          u11.val = 1ll * u11.cnt * (a[u11.id] - a[u11.id] / 2);
          a[u11.id] /= 2;
        }
      } else if (fg1) {
        ans++;
        now -= u11.val;
        u11.val = 1ll * u11.cnt * (a[u11.id] - a[u11.id] / 2);
        a[u11.id] /= 2;
      } else {
        ans += 2;
        now -= u2.val;
        u2.val = 1ll * u2.cnt * (a[u2.id] - a[u2.id] / 2);
        a[u2.id] /= 2;
      }
      if (fg1) {
        q1.push(u11);
        q1.push(u12);
      }
      if (fg2) q2.push(u2);
    }
    while (!q1.empty()) q1.pop();
    while (!q2.empty()) q2.pop();
    printf("%d\n", ans);
  }
}
