#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9 + 7;
const int inf = 1e9;
const int N = 1e5;
vector<long long int> tot(N);
vector<bool> vis(N);
vector<int> adj[N];
void dfs(int node) {
  vis[node] = true;
  for (auto &i : adj[node]) {
    if (!vis[i]) {
      dfs(i);
      tot[node] += tot[i];
    }
  }
  if ((int)adj[node].size() == 1 && node != 0) tot[node]++;
}
void solve() {
  vector<tuple<int, int, long long int, int>> vc;
  int n, u, v, x;
  long long int s, w;
  cin >> n >> s;
  for (int i = 0; i < n - 1; i++) {
    cin >> u >> v >> w >> x;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
    vc.push_back({u, v, w, x});
  }
  dfs(0);
  int cnt = 0;
  long long int sum = 0;
  priority_queue<tuple<long long int, long long int, long long int>> q1, q2;
  for (auto &i : vc) {
    u = get<0>(i);
    v = get<1>(i);
    w = get<2>(i);
    x = get<3>(i);
    long long int tp = min(tot[u], tot[v]);
    sum += tp * w;
    if (x == 1)
      q1.push({tp * w - tp * (w / 2), tp, w / 2});
    else
      q2.push({tp * w - tp * (w / 2), tp, w / 2});
  }
  long long int r1, r2, r3;
  while (sum > s) {
    tuple<long long int, long long int, long long int> x;
    tuple<long long int, long long int, long long int> y;
    r1 = r2 = r3 = 0;
    if (!q1.empty()) x = q1.top();
    if (!q2.empty()) y = q2.top();
    if (!q1.empty()) {
      long long int a = get<0>(x);
      long long int b = get<1>(x);
      long long int c = get<2>(x);
      r1 = a;
      q1.pop();
      if (q1.empty())
        r3 = b * c - b * (c / 2);
      else {
        r3 = max(get<0>(q1.top()), b * c - b * (c / 2));
      }
      q1.push(x);
    }
    if (!q2.empty()) r2 = get<0>(y);
    if (r1 >= r2 || sum - r1 <= s) {
      cnt++;
      long long int a = get<0>(x);
      long long int b = get<1>(x);
      long long int c = get<2>(x);
      sum -= a;
      q1.pop();
      q1.push({b * c - b * (c / 2), b, c / 2});
    } else {
      if (r1 + r3 >= r2) {
        long long int a = get<0>(x);
        long long int b = get<1>(x);
        long long int c = get<2>(x);
        sum -= a;
        q1.pop();
        q1.push({b * c - b * (c / 2), b, c / 2});
        cnt++;
      } else {
        long long int a = get<0>(y);
        long long int b = get<1>(y);
        long long int c = get<2>(y);
        sum -= a;
        q2.pop();
        q2.push({b * c - b * (c / 2), b, c / 2});
        cnt += 2;
      }
    }
  }
  cout << cnt << "\n";
  for (int i = 0; i < n; i++) {
    tot[i] = 0;
    vis[i] = false;
    adj[i].clear();
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
