#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20;
long long sum;
vector<long long> one, two;
vector<array<int, 3> > adj[N];
int dfs(int u, int p = -1) {
  if (int(adj[u].size()) == 1 && adj[u][0][0] == p) return 1;
  int ans = 0;
  for (auto ar : adj[u]) {
    int v = ar[0], w = ar[1], t = ar[2];
    if (v == p) continue;
    int leaf = dfs(v, u);
    ans += leaf;
    sum += 1LL * leaf * w;
    while (w > 0) {
      long long prev = 1LL * leaf * w;
      w /= 2;
      long long now = 1LL * leaf * w;
      if (t == 1)
        one.push_back(prev - now);
      else
        two.push_back(prev - now);
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    long long s;
    cin >> n >> s;
    one.clear();
    two.clear();
    for (int i = 0; i < int(n + 1); ++i) adj[i].clear();
    for (int i = 0; i < n - 1; ++i) {
      int u, v, w, t;
      cin >> u >> v >> w >> t;
      array<int, 3> e1 = {v, w, t}, e2 = {u, w, t};
      adj[u].push_back(e1);
      adj[v].push_back(e2);
    }
    sum = 0;
    dfs(1);
    if (sum <= s) {
      cout << 0 << '\n';
      continue;
    }
    sort(one.begin(), one.end());
    reverse(one.begin(), one.end());
    sort(two.begin(), two.end());
    reverse(two.begin(), two.end());
    vector<long long> psum(int(one.size()) + 1, 0);
    int ans = 1e9;
    for (int i = 1; i <= int(one.size()); ++i) {
      psum[i] = psum[i - 1] + one[i - 1];
      if (sum - psum[i] <= s) ans = min(ans, i);
    }
    for (int i = 0; i < int(two.size()); ++i) {
      sum -= two[i];
      long long left = sum - s;
      int other = lower_bound(psum.begin(), psum.end(), left) - psum.begin();
      if (other == int(psum.size())) continue;
      ans = min(ans, 2 * (i + 1) + other);
    }
    cout << ans << '\n';
  }
  return 0;
}
