#include <bits/stdc++.h>
using namespace std;
void solve() {
  int n;
  long long s;
  cin >> n >> s;
  vector<vector<pair<int, int>>> adj(n);
  vector<long long> weight(n - 1);
  vector<int> cnt(n - 1), cost(n - 1);
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v >> weight[i] >> cost[i];
    --u;
    --v;
    adj[u].emplace_back(v, i);
    adj[v].emplace_back(u, i);
  }
  function<void(int, int)> dfs = [&](int u, int edge) {
    if (edge != -1 && adj[u].size() == 1) cnt[edge] = 1;
    for (auto &[v, id] : adj[u]) {
      if (id == edge) continue;
      dfs(v, id);
      if (edge != -1) cnt[edge] += cnt[id];
    }
  };
  dfs(0, -1);
  auto get = [&](int i) { return 1LL * cnt[i] * ((weight[i] + 1) / 2); };
  vector<priority_queue<pair<long long, int>>> poss(2);
  long long total = 0;
  for (int i = 0; i < n - 1; ++i) {
    total += (1LL * cnt[i] * weight[i]);
    poss[(cost[i] == 2 ? 1 : 0)].emplace(get(i), i);
  }
  vector<long long> r[2];
  for (int i = 0; i < 2; ++i) {
    r[i].push_back(0);
    long long tmp = total;
    while (!poss[i].empty() && tmp > s) {
      auto [red, x] = poss[i].top();
      poss[i].pop();
      if (red == 0) break;
      r[i].push_back(r[i].back() + red);
      tmp -= red;
      weight[x] /= 2;
      poss[i].emplace(get(x), x);
    }
  }
  int ans = 1e9;
  for (int cnt1 = 0; cnt1 < (int)r[0].size(); ++cnt1) {
    auto it = lower_bound(r[1].begin(), r[1].end(),
                          (long long)total - s - r[0][cnt1]);
    if (it == r[1].end()) continue;
    int cnt2 = it - r[1].begin();
    ans = min(ans, (cnt1 + 2 * cnt2));
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
