#include <bits/stdc++.h>
using namespace std;
const long long max_n = 2e5 + 5;
long long n, s, sum;
vector<vector<pair<long long, long long> > > g;
vector<long long> sz, wt;
set<pair<long long, long long> > st1, st2;
map<pair<long long, long long>, long long> ec;
void dfs(long long rt, long long par = -1, long long w = 0) {
  sz[rt] = 0;
  if (g[rt].size() == 1 and par >= 0) sz[rt] = 1;
  for (auto ch : g[rt]) {
    if (ch.first == par) continue;
    dfs(ch.first, rt, ch.second);
    sz[rt] += sz[ch.first];
  }
  if (par >= 0) {
    sum += w * sz[rt];
    wt[rt] = w;
    w = (w / 2) + (w & 1);
    if (ec[{min(rt, par), max(rt, par)}] == 1)
      st1.insert({w * sz[rt] * (-1), rt});
    else
      st2.insert({w * sz[rt] * (-1), rt});
  }
}
long long get_val1() {
  if (st1.empty()) return 0;
  long long pos = (*st1.begin()).second;
  long long ans = ((wt[pos] / 4) - wt[pos]) * sz[pos];
  if (st1.size() > 1) {
    auto it = st1.begin();
    long long val = it->first;
    ++it;
    val += it->first;
    ans = min(ans, val);
  }
  return ans;
}
long long get_val2() {
  if (st2.empty()) return 0;
  return (*st2.begin()).first;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long tc;
  cin >> tc;
  while (tc--) {
    cin >> n >> s;
    g.resize(n);
    g.assign(n, vector<pair<long long, long long> >());
    sz.resize(n);
    sz.assign(n, 0);
    wt.resize(n);
    st1.clear();
    st2.clear();
    sum = 0;
    for (long long i = 1; (1 > 0 and i < n) or (1 < 0 and i > n); i += 1) {
      long long u, v, w, c;
      cin >> u >> v >> w >> c;
      g[--u].push_back({--v, w});
      g[v].push_back({u, w});
      ec[{min(u, v), max(u, v)}] = c;
    }
    dfs(0);
    long long cost = 0;
    while (sum > s) {
      if (!st1.empty() and (*st1.begin()).first <= s - sum) {
        cost += 1;
        pair<long long, long long> p = (*st1.begin());
        st1.erase(st1.begin());
        sum += p.first;
        wt[p.second] /= 2;
        long long w = (wt[p.second] / 2) + (wt[p.second] & 1);
        w *= sz[p.second] * (-1);
        st1.insert({w, p.second});
      } else if (get_val2() <= get_val1()) {
        cost += 2;
        pair<long long, long long> p = (*st2.begin());
        st2.erase(st2.begin());
        sum += p.first;
        wt[p.second] /= 2;
        long long w = (wt[p.second] / 2) + (wt[p.second] & 1);
        w *= sz[p.second] * (-1);
        st2.insert({w, p.second});
      } else {
        cost += 1;
        pair<long long, long long> p = (*st1.begin());
        st1.erase(st1.begin());
        sum += p.first;
        wt[p.second] /= 2;
        long long w = (wt[p.second] / 2) + (wt[p.second] & 1);
        w *= sz[p.second] * (-1);
        st1.insert({w, p.second});
      }
    }
    cout << cost << endl;
  }
  return 0;
}
