#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<long long int, long long int>, long long int>> g[100009];
multiset<pair<long long int, pair<long long int, long long int>>> s1, s2;
long long int sum1, sum2;
int dfs(long long int u, long long int p) {
  long long int nn = 0;
  bool is = true;
  for (auto it : g[u]) {
    long long int v = it.first.first, w = it.first.second, c = it.second;
    if (v != p) {
      is = false;
      long long int k = dfs(v, u);
      if (c == 1) {
        sum1 += (w * k);
        s1.insert({w * k - (w / 2) * k, {w, k}});
      } else {
        sum2 += (w * k);
        s2.insert({w * k - (w / 2) * k, {w, k}});
      }
      nn += k;
    }
  }
  if (is)
    return 1;
  else
    return nn;
}
long long int a1[2000009], a2[2000009];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int test;
  cin >> test;
  while (test--) {
    long long int n, s;
    cin >> n >> s;
    for (long long int i = 0; i <= n; i++) g[i].clear();
    s1.clear();
    s2.clear();
    for (long long int i = 1; i <= n - 1; i++) {
      long long int u, v, w, c;
      cin >> u >> v >> w >> c;
      g[u].push_back({{v, w}, c});
      g[v].push_back({{u, w}, c});
    }
    sum1 = 0, sum2 = 0;
    dfs(1, 0);
    long long int te = sum1;
    long long int i = 1;
    a1[0] = 0, a2[0] = 0;
    while (te > 0) {
      auto it = s1.end();
      it--;
      long long int ch = (*it).first, w = (*it).second.first,
                    k = (*it).second.second;
      a1[i] = ch + a1[i - 1];
      w = w / 2;
      te -= ch;
      if (ch == 0) break;
      s1.erase(it);
      s1.insert({w * k - (w / 2) * k, {w, k}});
      i++;
    }
    long long int max1 = i;
    te = sum2;
    i = 1;
    while (te > 0) {
      auto it = s2.end();
      it--;
      long long int ch = (*it).first, w = (*it).second.first,
                    k = (*it).second.second;
      a2[i] = ch + a2[i - 1];
      w = w / 2;
      te -= ch;
      if (ch == 0) break;
      s2.erase(it);
      s2.insert({w * k - (w / 2) * k, {w, k}});
      i++;
    }
    long long int max2 = i;
    long long int ans = 1e17;
    for (i = 0; i < max1; i++) {
      long long int st = sum1 + sum2;
      st -= a1[i];
      long long int p = lower_bound(a2, a2 + max2, st - s) - a2;
      if (p != max2) ans = min(ans, i + 2 * p);
    }
    cout << ans << endl;
  }
}
