#include <bits/stdc++.h>
using namespace std;
vector<long long> a[200009], fuck[2];
long long f[200009];
vector<pair<pair<long long, long long>, pair<long long, long long> > > adj;
long long go(int x, int pr) {
  if (x != 1 && a[x].size() == 1) return f[x] = 1;
  long long u = 0;
  for (int i = 0; i < a[x].size(); i++)
    if (a[x][i] != pr) u += go(a[x][i], x);
  return f[x] = u;
}
int main() {
  ios::sync_with_stdio(0);
  long long n, s, t;
  cin >> t;
  while (t--) {
    fuck[0].clear();
    fuck[1].clear();
    cin >> n >> s;
    adj.clear();
    for (int i = 1; i <= n; i++) a[i].clear();
    for (int i = 0; i < n - 1; i++) {
      long long u, v, w, c;
      cin >> u >> v >> w >> c;
      a[u].push_back(v);
      a[v].push_back(u);
      adj.push_back({{u, v}, {w, c}});
    }
    go(1, 0);
    long long rr = 0;
    for (int i = 0; i < n - 1; i++) {
      long long u = min(f[adj[i].first.first], f[adj[i].first.second]);
      long long v = adj[i].second.first;
      long long g = adj[i].second.second - 1;
      rr += u * v;
      while (v > 0) {
        long long ee = v / 2;
        long long p = u * v - (u * ee);
        fuck[g].push_back(p);
        v /= 2;
      }
    }
    sort(fuck[0].begin(), fuck[0].end());
    sort(fuck[1].begin(), fuck[1].end());
    long long l = fuck[0].size(), r = fuck[1].size();
    l--, r--;
    long long res = 1e18;
    while (l >= 0 && rr > s) {
      rr -= fuck[0][l];
      l--;
    }
    l++;
    if (rr <= s) {
      res = fuck[0].size() - l;
    }
    while (r >= 0) {
      rr -= fuck[1][r];
      if (rr <= s) {
        while (rr <= s && l < fuck[0].size()) {
          rr += fuck[0][l];
          l++;
        }
        if (rr > s) {
          l--;
          rr -= fuck[0][l];
        }
        long long pp = fuck[0].size() - l;
        pp += 2 * (fuck[1].size() - r);
        res = min(res, pp);
      }
      r--;
    }
    cout << res << '\n';
  }
  return 0;
}
