#include <bits/stdc++.h>
using namespace std;
int n;
long long s;
vector<long long> wt, cost, cnt;
vector<vector<pair<int, int> > > g;
long long getdiff(int i) { return (wt[i] * cnt[i] - (wt[i] / 2) * cnt[i]); }
void dfs(int u, int p = -1) {
  if (g[u].size() == 1) {
    if (p != -1) {
      cnt[p] = 1;
    }
  }
  for (int i = 0; i < g[u].size(); i++) {
    pair<int, int> nv = g[u][i];
    int to = nv.first;
    int id = nv.second;
    if (p == id) {
      continue;
    }
    dfs(to, id);
    if (p != -1) {
      cnt[p] += cnt[id];
    }
  }
}
vector<long long> get(int clr) {
  set<pair<long long, int> > st;
  long long curr = 0;
  for (int i = 0; i < n - 1; i++) {
    if (cost[i] == clr) {
      st.insert(make_pair(getdiff(i), i));
      curr += wt[i] * cnt[i];
    }
  }
  vector<long long> res;
  res.push_back(curr);
  while (curr > 0 && !st.empty()) {
    int id = st.rbegin()->second;
    st.erase(prev(st.end()));
    curr -= getdiff(id);
    res.push_back(curr);
    wt[id] /= 2;
    st.insert(make_pair(getdiff(id), id));
  }
  return res;
}
void solve(void) {
  dfs(0);
  vector<long long> v1 = get(1);
  vector<long long> v2 = get(2);
  long long ans = LLONG_MAX;
  int pos = v2.size() - 1;
  for (int i = 0; i < v1.size(); i++) {
    while (pos > 0 && v1[i] + v2[pos - 1] <= s) --pos;
    if (v1[i] + v2[pos] <= s) {
      ans = min(ans, i * 1LL + 2 * pos);
    }
  }
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int tt;
  cin >> tt;
  while (tt--) {
    wt.clear();
    cost.clear();
    g.clear();
    cnt.clear();
    cin >> n >> s;
    wt.resize(n);
    cost.resize(n);
    g.resize(n);
    cnt.resize(n, 0);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v >> wt[i] >> cost[i];
      --u;
      --v;
      g[u].push_back(make_pair(v, i));
      g[v].push_back(make_pair(u, i));
    }
    solve();
  }
  return 0;
}
