#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n;
long long s;
long long c[N];
vector<pair<int, int>> adj[N];
priority_queue<pair<long long, int>> q[2];
long long sum = 0;
long long chs[N], r[N];
long long rem(long long x, int ch) {
  long long nw = x / 2;
  return 1LL * (x - nw) * ch;
}
int dfs(int x, int p) {
  int sz = (adj[x].size() == 1);
  for (auto u : adj[x]) {
    if (u.first == p) continue;
    int cnt = dfs(u.first, x);
    sum += cnt * c[u.second];
    chs[u.second] = cnt;
    q[r[u.second] - 1].push({rem(c[u.second], cnt), u.second});
    sz += cnt;
  }
  return sz;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
      adj[i].clear();
    }
    while (q[0].size()) q[0].pop();
    while (q[1].size()) q[1].pop();
    sum = 0;
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v >> c[i] >> r[i];
      adj[u].push_back({v, i});
      adj[v].push_back({u, i});
    }
    dfs(1, 1);
    vector<long long> a1, a2;
    while (q[0].size()) {
      a1.push_back(q[0].top().first);
      pair<long long, int> tp = q[0].top();
      c[tp.second] /= 2LL;
      q[0].pop();
      if (c[tp.second])
        q[0].push({rem(c[tp.second], chs[tp.second]), tp.second});
    }
    while (q[1].size()) {
      a2.push_back(q[1].top().first);
      pair<long long, int> tp = q[1].top();
      c[tp.second] /= 2LL;
      q[1].pop();
      if (c[tp.second])
        q[1].push({rem(c[tp.second], chs[tp.second]), tp.second});
    }
    long long sm = 0;
    int ans = 0;
    if (sum > s) {
      ans = 1e8;
      int ret = 0;
      int j = 0;
      for (; j < (int)a2.size(); j++) {
        if (sum <= s) break;
        sum -= a2[j];
        ret += 2;
      }
      if (sum <= s) ans = min(ans, ret);
      for (int i = 0; i < (int)a1.size(); i++) {
        sum -= a1[i];
        ret++;
        while (j && a2.size() && sum + a2[j - 1] <= s) {
          ret -= 2;
          sum += a2[--j];
        }
        if (sum <= s) ans = min(ans, ret);
      }
    }
    cout << ans << " \n";
  }
  return 0;
}
