#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = array<ll, 3>;
vector<vector<pii>> adj;
vi sz, parent;
int fill(int cur, int par = -1) {
  parent[cur] = par;
  for (auto [v, _, __] : adj[cur])
    if (v != par) sz[cur] += fill(v, cur);
  sz[cur] = max(1, sz[cur]);
  return sz[cur];
}
int main(int argc, char* argv[]) {
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  int t;
  cin >> t;
  while (t--) {
    ll n, s;
    cin >> n >> s;
    adj.assign(n, {});
    sz.assign(n, 0);
    parent.assign(n, -1);
    for (int i = (0); i < (n - 1); ++i) {
      ll u, v, w, c;
      cin >> u >> v >> w >> c;
      u--, v--;
      adj[u].push_back({v, w, c});
      adj[v].push_back({u, w, c});
    }
    fill(0);
    priority_queue<array<ll, 3>> prePQ[2];
    ll start_sum = 0;
    for (int u = (0); u < (n); ++u)
      for (auto [v, w, c] : adj[u]) {
        if (parent[v] == u) {
          start_sum += w * sz[v];
          if (c == 1) {
            prePQ[0].push({sz[v] * (w - w / 2), w, sz[v]});
            prePQ[0].push({sz[v] * (w / 2 - w / 4), w / 2, sz[v]});
          } else {
            prePQ[1].push({sz[v] * (w - w / 2), w, sz[v]});
          }
        }
      }
    ll mi = 1e18;
    for (int p = (0); p < (2); ++p) {
      ll steps = 0, cur_sum = start_sum;
      priority_queue<array<ll, 3>> pqOne = prePQ[0], pqTwo = prePQ[1];
      if (p && pqOne.size()) {
        steps++;
        auto [g, w, s] = pqOne.top();
        w /= 4;
        cur_sum -= g;
        pqOne.pop();
        pqOne.push({s * (w - w / 2), w, s});
      }
      while (cur_sum > s) {
        if (pqOne.empty()) {
          steps += 2;
          auto [g, w, s] = pqTwo.top();
          w /= 2;
          cur_sum -= g;
          pqTwo.pop();
          pqTwo.push({s * (w - w / 2), w, s});
        } else if (pqTwo.empty()) {
          steps += 1;
          auto [g, w, s] = pqOne.top();
          w /= 4;
          cur_sum -= g;
          pqOne.pop();
          pqOne.push({s * (w - w / 2), w, s});
        } else {
          steps += 2;
          auto [g11, w11, s11] = pqOne.top();
          pqOne.pop();
          auto [g12, w12, s12] = pqOne.top();
          pqOne.pop();
          auto [g2, w2, s2] = pqTwo.top();
          pqTwo.pop();
          if (g11 + g12 > g2) {
            pqTwo.push({g2, w2, s2});
            cur_sum -= g11 + g12;
            w11 /= 4;
            w12 /= 4;
            pqOne.push({s11 * (w11 - w11 / 2), w11, s11});
            pqOne.push({s12 * (w12 - w12 / 2), w12, s12});
          } else {
            pqOne.push({g11, w11, s11});
            pqOne.push({g12, w12, s12});
            cur_sum -= g2;
            w2 /= 2;
            pqTwo.push({s2 * (w2 - w2 / 2), w2, s2});
          }
        }
      }
      mi = min(mi, steps);
    }
    cout << mi << '\n';
  }
  cout.flush();
  return 0;
}
