#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
long long currentSum = 0;
vector<pair<pair<long long, long long>, long long> > edges;
vector<pair<long long, long long> > adj[N];
long long type[N];
bool visited[N];
long long sz[N];
long long parent[N];
void dfs(long long s, long long dist, long long par) {
  if (!visited[s]) {
    visited[s] = 1;
    parent[s] = par;
    if (adj[s].size() == 1 && s != 0) {
      sz[s] = 1;
      currentSum += dist;
    }
    for (long long i = 0; i < adj[s].size(); i++) {
      if (visited[adj[s][i].first]) continue;
      dfs(adj[s][i].first, dist + adj[s][i].second, s);
      sz[s] += sz[adj[s][i].first];
    }
  }
}
long long calcProf(pair<long long, pair<long long, long long> > p) {
  return p.second.second * p.second.first -
         p.second.second * (p.second.first / 2);
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long n, second;
    cin >> n >> second;
    edges.clear();
    currentSum = 0;
    for (long long i = 0; i < n; i++) {
      adj[i].clear();
      visited[i] = 0;
      sz[i] = 0;
      parent[i] = 0;
      type[i] = 0;
    }
    for (long long i = 0; i < n - 1; i++) {
      long long a, b, c, d;
      cin >> a >> b >> c >> d;
      a--;
      b--;
      adj[a].push_back({b, c});
      adj[b].push_back({a, c});
      type[i] = d;
      edges.push_back({{a, b}, c});
    }
    dfs(0, 0, -1);
    priority_queue<pair<long long, pair<long long, long long> > > cost1;
    priority_queue<pair<long long, pair<long long, long long> > > cost2;
    for (long long i = 0; i < n - 1; i++) {
      long long subTreeSz;
      long long a = edges[i].first.first;
      long long b = edges[i].first.second;
      if (parent[a] == b) {
        subTreeSz = sz[a];
      } else {
        subTreeSz = sz[b];
      }
      long long currentWeight = edges[i].second;
      long long profit =
          subTreeSz * currentWeight - subTreeSz * (currentWeight / 2);
      if (type[i] == 1) {
        cost1.push({profit, {currentWeight, subTreeSz}});
      } else {
        cost2.push({profit, {currentWeight, subTreeSz}});
      }
    }
    long long ans = 0;
    while (currentSum > second) {
      if (cost1.empty()) {
        ans += 2;
        pair<long long, pair<long long, long long> > p = cost2.top();
        cost2.pop();
        currentSum -= p.first;
        p.second.first /= 2;
        long long newProfit = calcProf(p);
        cost2.push({newProfit, {p.second.first, p.second.second}});
      } else if (cost2.empty()) {
        ans++;
        pair<long long, pair<long long, long long> > p = cost1.top();
        cost1.pop();
        currentSum -= p.first;
        p.second.first /= 2;
        long long newProfit = calcProf(p);
        cost1.push({newProfit, {p.second.first, p.second.second}});
      } else {
        pair<long long, pair<long long, long long> > ch1 = cost1.top();
        if (currentSum - ch1.first <= second) {
          currentSum -= ch1.first;
          ans++;
          break;
        }
        cost1.pop();
        long long pp1 = ch1.first;
        if (cost1.empty()) {
          pair<long long, pair<long long, long long> > ch11 = ch1;
          ch11.second.first /= 2;
          pp1 += calcProf(ch11);
        } else {
          pair<long long, pair<long long, long long> > ch11 = ch1;
          ch11.second.first /= 2;
          pair<long long, pair<long long, long long> > ch111 = cost1.top();
          pp1 += max(calcProf(ch11), calcProf(ch111));
        }
        if (pp1 > cost2.top().first) {
          ans++;
          currentSum -= ch1.first;
          ch1.second.first /= 2;
          ch1.first = calcProf(ch1);
          cost1.push(ch1);
        } else {
          ans += 2;
          cost1.push(ch1);
          pair<long long, pair<long long, long long> > ch2 = cost2.top();
          cost2.pop();
          currentSum -= ch2.first;
          ch2.second.first /= 2;
          ch2.first = calcProf(ch2);
          cost2.push(ch2);
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}
