#include <bits/stdc++.h>
using namespace std;
const long long maxm = 2e6 + 5;
struct E {
  long long v, w, c;
};
struct Node {
  long long w, cnt;
  bool operator<(const Node& a) const {
    return w * cnt - w / 2 * cnt < a.w * a.cnt - a.w / 2 * a.cnt;
  }
};
priority_queue<Node> q, qq;
vector<E> g[maxm];
long long sz[maxm];
long long temp1[maxm], c1;
long long temp2[maxm], c2;
long long n, S;
long long sum;
void init() {
  sum = 0;
  c1 = c2 = 0;
  while (!q.empty()) q.pop();
  while (!qq.empty()) qq.pop();
  for (long long i = 1; i <= n; i++) {
    g[i].clear();
  }
}
void dfs(long long x, long long fa) {
  sz[x] = 0;
  if (g[x].size() == 1 && x != 1) {
    sz[x] = 1;
    return;
  }
  for (auto i : g[x]) {
    long long v = i.v;
    if (v == fa) continue;
    dfs(v, x);
    sum += i.w * sz[v];
    sz[x] += sz[v];
    if (i.c == 1) {
      q.push({i.w, sz[v]});
    } else {
      qq.push({i.w, sz[v]});
    }
  }
}
signed main() {
  ios::sync_with_stdio(0);
  long long T;
  cin >> T;
  while (T--) {
    init();
    cin >> n >> S;
    for (long long i = 1; i < n; i++) {
      long long a, b, c, d;
      cin >> a >> b >> c >> d;
      g[a].push_back({b, c, d});
      g[b].push_back({a, c, d});
    }
    dfs(1, 1);
    if (sum <= S) {
      cout << 0 << endl;
      continue;
    }
    while (!q.empty()) {
      Node x = q.top();
      q.pop();
      long long t = x.w * x.cnt - x.w / 2 * x.cnt;
      temp1[++c1] = t;
      temp1[c1] += temp1[c1 - 1];
      if (sum - temp1[c1] <= S) break;
      x.w /= 2;
      if (x.w) q.push(x);
    }
    while (!qq.empty()) {
      Node x = qq.top();
      qq.pop();
      long long t = x.w * x.cnt - x.w / 2 * x.cnt;
      temp2[++c2] = t;
      temp2[c2] += temp2[c2 - 1];
      if (sum - temp2[c2] <= S) break;
      x.w /= 2;
      if (x.w) qq.push(x);
    }
    long long ans = 1e18;
    for (long long i = 0; i <= c1; i++) {
      long long ss = sum - temp1[i];
      long long l = 0, r = c2;
      long long pos = 1e18;
      while (l <= r) {
        long long mid = (l + r) / 2;
        if (ss - temp2[mid] <= S)
          pos = mid, r = mid - 1;
        else
          l = mid + 1;
      }
      ans = min(ans, i + pos * 2);
    }
    cout << ans << endl;
  }
  return 0;
}
