#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
  long long n, S;
  cin >> n >> S;
  vector<vector<pair<long long, pair<long long, long long>>>> g(n);
  for (long long i = 1; i < n; i++) {
    long long v, u, w, c;
    cin >> v >> u >> w >> c;
    v--;
    u--;
    g[v].push_back({u, make_pair(w, c)});
    g[u].push_back({v, make_pair(w, c)});
  }
  vector<vector<pair<long long, long long>>> kek(2);
  vector<vector<long long>> ans(2);
  function<long long(long long, long long)> dfs = [&](long long v,
                                                      long long p) {
    long long ret = 0;
    for (auto i : g[v]) {
      long long u = i.first, w = i.second.first, c = i.second.second;
      if (u == p) continue;
      long long val = dfs(u, v);
      kek[c - 1].push_back({val, w});
      ret += val;
    }
    if (ret == 0) ret = 1;
    return ret;
  };
  dfs(0, -1);
  for (long long it = 0; it < 2; it++) {
    long long cur_sum = 0;
    for (auto i : kek[it]) {
      cur_sum += i.first * i.second;
    }
    priority_queue<pair<long long, pair<long long, long long>>> s;
    for (auto i : kek[it]) {
      s.push(make_pair(i.first * (i.second - i.second / 2),
                       make_pair(i.first, i.second)));
    }
    ans[it].push_back(cur_sum);
    while (cur_sum > 0) {
      assert((long long)s.size());
      long long k = s.top().second.first, x = s.top().second.second;
      s.pop();
      cur_sum -= k * x;
      x /= 2;
      cur_sum += k * x;
      if (x) s.push(make_pair(k * (x - x / 2), make_pair(k, x)));
      ans[it].push_back(cur_sum);
    }
    ans[it].push_back(cur_sum);
  }
  const long long INF = 1e9;
  long long res = INF;
  for (long long i = 0, j = (long long)ans[1].size() - 1;
       i < (long long)ans[0].size(); i++) {
    while (j >= 0 && ans[1][j] + ans[0][i] <= S) j--;
    if (j != (long long)ans[1].size() - 1 && ans[0][i] + ans[1][j + 1] <= S)
      res = min(res, i + 2 * (j + 1));
  }
  cout << res << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long q;
  cin >> q;
  while (q--) {
    solve();
  }
}
