#include <bits/stdc++.h>
using namespace std;
const int N = 100007;
vector<pair<int, pair<long long, int>>> v[N];
long long n, s, sum = 0, cnt = 0, id = 0;
priority_queue<pair<pair<long long, long long>, long long>> pq[3];
void solve(int k) {
  auto p = pq[k].top();
  pq[k].pop();
  sum -= p.first.first;
  cnt += k;
  long long w1 = p.first.second / 2;
  p.first.second = w1;
  p.first.first = (w1 * p.second - w1 / 2 * p.second);
  pq[k].push(p);
}
int dfs(int x, int p, long long w, int ty) {
  long long c = (x != 1 && v[x].size() == 1);
  for (auto i : v[x]) {
    if (i.first != p) c += dfs(i.first, x, i.second.first, i.second.second);
  }
  if (p != -1) {
    pq[ty].push({{w * c - w / 2 * c, w}, c});
    sum += w * c;
  }
  return c;
}
void init() {
  for (int i = 0; i <= n + 5; i++) v[i].clear();
  while (pq[1].size()) pq[1].pop();
  while (pq[2].size()) pq[2].pop();
  sum = cnt = 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> s;
    init();
    for (int i = 0; i < n - 1; i++) {
      int x, y, z, ty;
      cin >> x >> y >> z >> ty;
      v[x].push_back({y, {z, ty}});
      v[y].push_back({x, {z, ty}});
    }
    pq[1].push({{0, 0}, 0});
    pq[1].push({{0, 0}, 0});
    pq[2].push({{0, 0}, 0});
    pq[2].push({{0, 0}, 0});
    dfs(1, -1, 0, 0);
    while (sum > s) {
      if (sum - pq[1].top().first.first <= s ||
          pq[1].top().first.first >= pq[2].top().first.first)
        solve(1);
      else {
        auto p = pq[1].top(), pp = p;
        pq[1].pop();
        p.first.second /= 2;
        p.first.first =
            p.first.second * p.second - p.first.second / 2 * p.second;
        if (max(p.first.first, pq[1].top().first.first) + pp.first.first >=
            pq[2].top().first.first) {
          pq[1].push(pp);
          solve(1);
        } else {
          pq[1].push(pp);
          solve(2);
        }
      }
    }
    cout << cnt << "\n";
  }
}
