#include <bits/stdc++.h>
using namespace std;
struct node {
  bool used = 0;
  vector<pair<long long, pair<long long, long long>>> edjes;
};
vector<node> g;
vector<long long> ctr, to, group;
long long sum = 0, way = 0;
void dfs(long long start) {
  g[start].used = 1;
  if (g[start].edjes.size() == 1) {
    ctr[start]++;
    sum += way;
  }
  for (auto &i : g[start].edjes) {
    if (g[i.first].used) continue;
    way += i.second.first;
    dfs(i.first);
    way -= i.second.first;
    to[i.first] = i.second.first;
    group[i.first] = i.second.second;
    ctr[start] += ctr[i.first];
  }
}
const long long INF = 1e18;
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long n, s;
    cin >> n >> s;
    g.clear();
    g.resize(n);
    for (long long i = 0; i < n - 1; i++) {
      long long a, b, w, c;
      cin >> a >> b >> w >> c;
      a--;
      b--;
      g[a].edjes.push_back({b, {w, c}});
      g[b].edjes.push_back({a, {w, c}});
    }
    sum = 0;
    ctr.clear();
    to.clear();
    ctr.resize(n);
    to.resize(n);
    group.clear();
    group.resize(n);
    dfs(0);
    if (sum <= s)
      cout << 0 << '\n';
    else {
      sum -= s;
      multiset<pair<long long, long long>> fir, sec;
      for (long long i = 0; i < n; i++) {
        if (group[i] == 1)
          fir.insert({(to[i] + 1) / 2 * ctr[i], i});
        else
          sec.insert({(to[i] + 1) / 2 * ctr[i], i});
      }
      long long now = 0;
      vector<long long> order;
      order.push_back(0);
      auto to2 = to;
      while (!fir.empty()) {
        long long ind = fir.rbegin()->second;
        long long delt = fir.rbegin()->first;
        fir.erase(*fir.rbegin());
        to[ind] /= 2;
        fir.insert({(to[ind] + 1) / 2 * ctr[ind], ind});
        if (delt == 0) break;
        now += delt;
        order.push_back(now);
      }
      now = 0;
      long long ans = INF, cur = 0;
      auto it = lower_bound((order).begin(), (order).end(), sum);
      if (it != order.end()) ans = it - order.begin();
      to = to2;
      while (!sec.empty()) {
        long long ind = sec.rbegin()->second;
        long long delt = sec.rbegin()->first;
        sec.erase(*sec.rbegin());
        to[ind] /= 2;
        sec.insert({(to[ind] + 1) / 2 * ctr[ind], ind});
        now += delt;
        if (delt == 0) break;
        cur++;
        long long need = sum - now;
        auto it = lower_bound((order).begin(), (order).end(), need);
        if (it != order.end()) ans = min(ans, 2 * cur + (it - order.begin()));
      }
      cout << ans << '\n';
    }
  }
  return 0;
}
