#include <bits/stdc++.h>
using namespace std;
long long int mod = 1000000007;
void __print(long long int x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename Th, typename V>
void __print(const pair<Th, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename Th>
void __print(const Th &x) {
  long long int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename Th, typename... V>
void _print(Th t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
vector<vector<pair<long long int, pair<long long int, long long int>>>> edge;
vector<pair<long long int, long long int>> a;
vector<long long int> leaf;
long long int n, sum;
void dfs(long long int v, long long int p) {
  long long int bach = 0;
  for (auto it : edge[v]) {
    if (it.first == p) continue;
    a[it.first].first = it.second.first;
    a[it.first].second = it.second.second;
    dfs(it.first, v);
    bach += leaf[it.first];
  }
  if (edge[v].size() == 1) {
    bach = 1;
  } else {
  }
  leaf[v] = bach;
}
void binary_rock() {
  leaf.clear();
  edge.clear();
  a.clear();
  cin >> n >> sum;
  edge.resize(n);
  a.resize(n);
  leaf.resize(n);
  long long int i, j, k, l;
  long long int m = n - 1;
  for (i = 0; i < m; i++) {
    cin >> j >> k >> l;
    j--;
    k--;
    long long int ww;
    cin >> ww;
    edge[j].push_back({k, {l, ww}});
    edge[k].push_back({j, {l, ww}});
  }
  dfs(0, 0);
  ;
  ;
  multiset<pair<long long int, pair<long long int, long long int>>> sa;
  multiset<pair<long long int, pair<long long int, long long int>>> sb;
  long long int abhi = 0;
  for (i = 1; i < n; i++) {
    abhi += (leaf[i] * a[i].first);
    long long int cost = a[i].first * leaf[i];
    long long int fayda;
    long long int rem = (a[i].first) / 2;
    fayda = a[i].first - rem;
    fayda *= leaf[i];
    pair<long long int, pair<long long int, long long int>> p;
    p.first = fayda;
    p.second.first = a[i].first;
    p.second.second = leaf[i];
    if (a[i].second == 1)
      sa.insert(p);
    else {
      sb.insert(p);
    }
  }
  long long int ans = 0;
  vector<long long int> posa, posb;
  while (1) {
    if (sa.size() == 0) {
      break;
    }
    auto it = sa.end();
    it--;
    auto jt = (*it);
    sa.erase(it);
    if (jt.first <= 0) break;
    posa.push_back(jt.first);
    long long int cc = jt.second.first;
    cc = cc / 2;
    long long int rem = cc / 2;
    long long int ff = (jt.second.second * (cc - rem));
    sa.insert({ff, {cc, jt.second.second}});
  }
  while (1) {
    if (sb.size() == 0) break;
    auto it = sb.end();
    it--;
    auto jt = (*it);
    sb.erase(it);
    if (jt.first <= 0) break;
    posb.push_back(jt.first);
    long long int cc = jt.second.first;
    cc = cc / 2;
    long long int rem = cc / 2;
    long long int ff = (jt.second.second * (cc - rem));
    sb.insert({ff, {cc, jt.second.second}});
  }
  posa.push_back(00);
  posb.push_back(0);
  ;
  ;
  ;
  if (sum >= abhi) {
    cout << ans << endl;
  } else {
    ans = INT64_MAX;
    long long int nn = posa.size();
    long long int mm = posb.size();
    vector<long long int> ca(nn), cb(mm);
    ca[0] = posa[0];
    for (i = 1; i < nn; i++) {
      ca[i] = ca[i - 1];
      ca[i] += posa[i];
    }
    cb[0] = posb[0];
    for (i = 1; i < mm; i++) {
      cb[i] = cb[i - 1] + posb[i];
    }
    long long int req = abhi - sum;
    for (i = 0; i < nn; i++) {
      long long int curr = 0;
      long long int iska = (ca[i]);
      long long int rem = req - iska;
      auto it = lower_bound(cb.begin(), cb.end(), rem);
      if (it == cb.end()) continue;
      curr = i + 1;
      if (i == nn - 1) curr--;
      long long int idx = it - cb.begin();
      if (idx == mm - 1) curr -= 2;
      curr += idx + 1;
      curr += idx + 1;
      ans = min(ans, curr);
    }
    auto it = lower_bound(ca.begin(), ca.end(), req);
    if (it != ca.end()) ans = min(ans, (long long int)(it - ca.begin()) + 1);
    auto jt = lower_bound(cb.begin(), cb.end(), req);
    if (jt != cb.end())
      ans = min(ans, ((long long int)(jt - cb.begin()) + 1) * 2);
    cout << ans << endl;
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  clock_t t1 = clock();
  long long int t = 1;
  cin >> t;
  while (t--) {
    binary_rock();
  }
  clock_t t2 = clock();
  return 0;
}
