#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5 + 10;
class Edge {
 public:
  long long dest, weight, cost;
  Edge() {
    dest = 0;
    weight = 0;
    cost = 0;
  }
};
class Compare {
 public:
  bool operator()(pair<long long, long long>& a,
                  pair<long long, long long>& b) {
    long long cura = a.first * a.second;
    long long curb = b.first * b.second;
    long long futa = (a.first / 2) * a.second;
    long long futb = (b.first / 2) * b.second;
    return (cura - futa) < (curb - futb);
  }
};
vector<Edge> adj[MAXN];
long long numLeaves[MAXN], par[MAXN];
bool visited[MAXN];
void dfs(long long cur) {
  visited[cur] = true;
  if (adj[cur].size() == 1 && visited[adj[cur][0].dest]) {
    numLeaves[cur] = 1;
    return;
  }
  numLeaves[cur] = 0;
  for (auto i : adj[cur]) {
    if (!visited[i.dest]) {
      par[i.dest] = cur;
      dfs(i.dest);
      numLeaves[cur] += numLeaves[i.dest];
    }
  }
}
void solve() {
  long long n, s;
  cin >> n >> s;
  for (long long i = 0; i < n + 1; i++) {
    adj[i].clear();
    numLeaves[i] = 0;
    par[i] = -1;
    visited[i] = false;
  }
  for (long long i = 1; i < n; i++) {
    long long x, y, w, c;
    cin >> x >> y >> w >> c;
    x--, y--;
    Edge cur;
    cur.dest = y;
    cur.weight = w;
    cur.cost = c;
    adj[x].push_back(cur);
    cur.dest = x;
    adj[y].push_back(cur);
  }
  dfs(0);
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 Compare>
      oneCost, twoCost;
  long long sum = 0;
  for (long long i = 0; i < n; i++) {
    for (auto j : adj[i]) {
      if (par[j.dest] == i) {
        sum += (numLeaves[j.dest]) * (j.weight);
        if (j.cost == 1)
          oneCost.push(make_pair(j.weight, numLeaves[j.dest]));
        else
          twoCost.push(make_pair(j.weight, numLeaves[j.dest]));
      }
    }
  }
  vector<long long> oneDif, twoDif;
  while (!oneCost.empty()) {
    pair<long long, long long> cur = oneCost.top();
    oneCost.pop();
    long long fut = (cur.first / 2) * (cur.second);
    long long dif = (cur.first) * (cur.second) - fut;
    oneDif.push_back(dif);
    cur.first /= 2;
    if (cur.first != 0) oneCost.push(cur);
  }
  while (!twoCost.empty()) {
    pair<long long, long long> cur = twoCost.top();
    twoCost.pop();
    long long fut = (cur.first / 2) * (cur.second);
    long long dif = (cur.first) * (cur.second) - fut;
    twoDif.push_back(dif);
    cur.first /= 2;
    if (cur.first != 0) twoCost.push(cur);
  }
  long long cost = LLONG_MAX;
  for (long long i = 1; i < oneDif.size(); i++) oneDif[i] += oneDif[i - 1];
  for (long long i = 1; i < twoDif.size(); i++) twoDif[i] += twoDif[i - 1];
  if (sum <= s) cost = 0;
  long long l = 0, h = twoDif.size() - 1;
  long long ans = -1;
  while (l <= h) {
    long long mid = (l + h) / 2;
    if (sum - twoDif[mid] <= s) {
      ans = mid;
      h = mid - 1;
    } else
      l = mid + 1;
  }
  if (ans != -1) {
    cost = min(cost, 2 * (ans + 1));
  }
  for (long long i = 0; i < oneDif.size(); i++) {
    long long l = 0, h = twoDif.size() - 1;
    long long cur = sum - oneDif[i];
    if (cur <= s) {
      cost = min(cost, i + 1);
      break;
    }
    long long ans = -1;
    while (l <= h) {
      long long mid = (l + h) / 2;
      if (cur - twoDif[mid] <= s) {
        ans = mid;
        h = mid - 1;
      } else
        l = mid + 1;
    }
    if (ans != -1) {
      long long temp = (i + 1) + (ans + 1) * 2;
      cost = min(temp, cost);
    }
  }
  cout << cost << "\n";
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    solve();
  }
}
