#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
long long n, second, leaf[N], cost[N], coins[N];
vector<pair<long long, pair<long long, long long> > > adj[N];
int dfs(int node, int par, int cst, int ty) {
  if (node != 1) cost[node] = cst, coins[node] = ty;
  if (adj[node].size() == 1 && node != 1) {
    leaf[node] = 1;
    return 1;
  }
  for (auto ch : adj[node]) {
    if (ch.first != par) {
      dfs(ch.first, node, ch.second.first, ch.second.second);
      leaf[node] += leaf[ch.first];
    }
  }
  return leaf[node];
}
void cl() {
  for (int i = 0; i <= n; i++) {
    adj[i].clear();
    leaf[i] = 0;
    cost[i] = 0;
  }
}
long long solve(long long val, vector<long long> &v) {
  if (val <= 0) return 0;
  long long up = upper_bound(v.begin(), v.end(), val - 1) - v.begin();
  if (up == v.size()) return 1e18;
  return up + 1;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    cin >> n >> second;
    for (int i = 1; i < n; i++) {
      int x, y, c, cc;
      cin >> x >> y >> c >> cc;
      adj[x].push_back({y, {c, cc}}), adj[y].push_back({x, {c, cc}});
    }
    dfs(1, 1, 0, 0);
    long long ans = 0, sum = 0;
    priority_queue<pair<long long, pair<long long, long long> > > q, q2;
    for (int i = 2; i <= n; i++) {
      long long tmp = cost[i] * leaf[i] - (cost[i] / 2) * leaf[i];
      sum += cost[i] * leaf[i];
      if (coins[i] == 1)
        q.push({tmp, {cost[i], leaf[i]}});
      else
        q2.push({tmp, {cost[i], leaf[i]}});
    }
    pair<long long, pair<long long, long long> > pr;
    long long tmp;
    vector<long long> v, v2;
    while (q.size() && q.top().first > 0) {
      pr = q.top();
      q.pop();
      v.push_back(pr.first);
      pr.second.first /= 2;
      q.push({pr.second.first * pr.second.second -
                  (pr.second.first / 2) * pr.second.second,
              {pr.second.first, pr.second.second}});
    }
    while (q2.size() && q2.top().first > 0) {
      pr = q2.top();
      q2.pop();
      v2.push_back(pr.first);
      pr.second.first /= 2;
      q2.push({pr.second.first * pr.second.second -
                   (pr.second.first / 2) * pr.second.second,
               {pr.second.first, pr.second.second}});
    }
    for (int i = 1; i < (int)v.size(); i++) {
      v[i] += v[i - 1];
    }
    for (int i = 1; i < (int)v2.size(); i++) {
      v2[i] += v2[i - 1];
    }
    tmp = sum - second;
    ans = solve(tmp, v2) * 2;
    ans = min(ans, solve(tmp, v));
    long long curDif;
    for (int i = 0; i < (int)v.size(); i++) {
      curDif = tmp - v[i];
      ans = min(ans, solve(curDif, v2) * 2 + (i + 1));
    }
    cout << ans << '\n';
    cl();
  }
  return 0;
}
