#include <bits/stdc++.h>
using namespace std;
ostream& operator<<(ostream& str, const pair<long long, long long>& p) {
  str << p.first << " " << p.second;
  return str;
}
template <typename T>
void join(T& arr, string sep) {
  bool first = true;
  for (auto t : arr) {
    if (first) {
      first = false;
      cout << t;
    } else {
      cout << sep << t;
    }
  }
  cout << "\n";
}
const long long md = 1e9 + 7;
long long MOD(long long x) {
  long long r = x % md;
  if (r < 0) {
    r += md;
  }
  return r;
}
void solve() {
  long long n, s;
  cin >> n >> s;
  long long res = 0;
  vector<vector<vector<long long>>> g(n);
  for (long long i = 0; i < (long long)(n - 1); ++i) {
    long long u, v, w, c;
    cin >> u >> v >> w >> c;
    u--;
    v--;
    g[u].push_back({v, w, c});
    g[v].push_back({u, w, c});
  }
  priority_queue<vector<long long>> pq1;
  priority_queue<vector<long long>> pq2;
  long long cur = 0;
  function<long long(long long, long long)> helper = [&](long long u,
                                                         long long p) {
    long long path = 0;
    for (auto& vw : g[u]) {
      long long v = vw[0];
      if (v == p) continue;
      long long w = vw[1];
      long long c = vw[2];
      long long count = helper(v, u);
      path += count;
      long long nw = w / 2;
      if (c == 1) {
        pq1.push({w * count - nw * count, nw, count});
      } else {
        pq2.push({w * count - nw * count, nw, count});
      }
      cur += w * count;
    }
    return path == 0ll ? 1ll : path;
  };
  helper(0, -1);
  while (cur > s) {
    if (pq2.empty()) {
      vector<long long> t = pq1.top();
      pq1.pop();
      cur -= t[0];
      long long w = t[1];
      long long count = t[2];
      long long nw = w / 2;
      pq1.push({w * count - nw * count, nw, count});
      res++;
      continue;
    }
    if (pq1.empty()) {
      vector<long long> t = pq2.top();
      pq2.pop();
      cur -= t[0];
      long long w = t[1];
      long long count = t[2];
      long long nw = w / 2;
      pq2.push({w * count - nw * count, nw, count});
      res += 2;
      continue;
    }
    vector<long long> t = pq1.top();
    if (cur - t[0] <= s) {
      res++;
      break;
    }
    pq1.pop();
    long long c12;
    if (pq1.empty()) {
      c12 = -1e18;
    } else {
      c12 = t[0] + pq1.top()[0];
    }
    long long c11 = t[0] + (t[1] * t[2] - (t[1] / 2) * t[2]);
    long long c2 = pq2.top()[0];
    if (c2 >= c12 && c2 >= c11) {
      pq1.push(t);
      t = pq2.top();
      pq2.pop();
      cur -= t[0];
      long long w = t[1];
      long long count = t[2];
      long long nw = w / 2;
      pq2.push({w * count - nw * count, nw, count});
      res += 2;
    } else {
      cur -= t[0];
      long long w = t[1];
      long long count = t[2];
      long long nw = w / 2;
      pq1.push({w * count - nw * count, nw, count});
      res++;
    }
  }
  cout << res << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  cin >> tt;
  for (int t = 1; t <= tt; t++) {
    solve();
  }
  return 0;
}
