#include <bits/stdc++.h>
using namespace std;
vector<long long> v[2], adj[100005], cst[100005], weight[100005];
int leaf[100005];
vector<pair<long long, long long> > vec[2];
void dfs(int x, int p) {
  leaf[x] = 0;
  leaf[x] = (x != 1 && adj[x].size() == 1);
  for (int i = 0; i < adj[x].size(); i++) {
    int y = adj[x][i];
    if (y != p) {
      dfs(y, x), leaf[x] += leaf[y];
      if (cst[x][i] == 1)
        vec[0].push_back({leaf[y], weight[x][i]});
      else
        vec[1].push_back({leaf[y], weight[x][i]});
    }
  }
  return;
}
void func(bool f) {
  priority_queue<pair<long long, pair<long long, long long> > > pq;
  long long sum = 0;
  for (int i = 0; i < vec[f].size(); i++) {
    long long c1 = vec[f][i].first * vec[f][i].second;
    sum += c1;
    long long c2 = vec[f][i].first * (vec[f][i].second / 2);
    pq.push({c1 - c2, vec[f][i]});
  }
  if (sum) v[f].push_back(sum);
  while (!pq.empty()) {
    pair<long long, pair<long long, long long> > p = pq.top();
    pq.pop();
    sum -= (p.second.first * p.second.second);
    p.second.second /= 2;
    long long c1 = p.second.first * p.second.second;
    sum += c1;
    v[f].push_back(sum);
    long long c2 = p.second.first * (p.second.second / 2);
    p.first = c1 - c2;
    if (p.first) pq.push(p);
  }
  v[f].push_back(0);
  return;
}
int main() {
  int ts;
  scanf("%d", &ts);
  while (ts--) {
    int n;
    long long s;
    scanf("%d %lld", &n, &s);
    v[0].clear(), vec[0].clear();
    v[1].clear(), vec[1].clear();
    for (int i = 1; i <= n; i++)
      adj[i].clear(), cst[i].clear(), weight[i].clear();
    for (int i = 1; i < n; i++) {
      int x, y, a, b;
      scanf("%d %d %d %d", &x, &y, &a, &b);
      adj[x].push_back(y);
      adj[y].push_back(x);
      cst[x].push_back(b);
      cst[y].push_back(b);
      weight[x].push_back(a);
      weight[y].push_back(a);
    }
    dfs(1, 0);
    func(0);
    func(1);
    int res = 1000000009;
    for (int i = 0, j = v[1].size() - 1; i < v[0].size(); i++)
      if (v[0][i] <= s) {
        while (j >= 0 && (v[0][i] + v[1][j]) <= s) j--;
        j++;
        res = min(res, i + j * 2);
      }
    printf("%d\n", res);
  }
  return 0;
}
