#include <bits/stdc++.h>
using namespace std;
vector<pair<int, pair<int, int>>> adj[(long)(1e5)];
int sub[(long)(1e5)];
int w[(long)(1e5)];
int c[(long)(1e5)];
int dfs(int r, int p) {
  int cnt = 0;
  for (int i = 0; i < adj[r].size(); i++) {
    if (adj[r][i].first != p) {
      w[adj[r][i].first] = adj[r][i].second.first;
      c[adj[r][i].first] = adj[r][i].second.second;
      cnt += dfs(adj[r][i].first, r);
    }
  }
  if (!cnt) cnt = 1;
  sub[r] = cnt;
  return cnt;
}
void solve() {
  int n;
  long long s;
  scanf("%d%lld", &n, &s);
  for (int i = 0; i < n; i++) adj[i].clear();
  for (int i = 0; i < n - 1; i++) {
    int u, v, ww, cc;
    scanf("%d%d%d%d", &u, &v, &ww, &cc);
    adj[u - 1].push_back({v - 1, {ww, cc}});
    adj[v - 1].push_back({u - 1, {ww, cc}});
  }
  for (int i = 0; i < n; i++) sub[i] = 0;
  dfs(0, -1);
  vector<long long> vs[2];
  for (int k = 0; k < 2; k++) {
    long long sum = 0;
    set<pair<long long, int>> di;
    for (int i = 1; i < n; i++) {
      if (c[i] == k + 1) {
        di.insert({(1ll * sub[i] * w[i] - 1ll * sub[i] * (w[i] / 2)), i});
        sum += 1ll * sub[i] * w[i];
      }
    }
    vs[k].push_back(sum);
    while (sum > 0) {
      int i = di.rbegin()->second;
      long long decr = di.rbegin()->first;
      di.erase(prev(di.end()));
      sum -= decr;
      w[i] = w[i] / 2;
      di.insert({(1ll * sub[i] * w[i] - 1ll * sub[i] * (w[i] / 2)), i});
      vs[k].push_back(sum);
    }
  }
  int flip = 0;
  if (vs[0].size() > vs[1].size()) {
    swap(vs[1], vs[0]);
    flip = 1;
  }
  int ans = 1e9;
  for (int i = 0; i < vs[0].size(); i++) {
    int lo = 0, hi = vs[1].size() - 1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (vs[0][i] + vs[1][mid] <= s)
        hi = mid - 1;
      else
        lo = mid + 1;
    }
    if (vs[0][i] + vs[1][lo] <= s)
      ans = min(ans, i * (1 + flip) + lo * (2 - flip));
  }
  printf("%d\n", ans);
}
int main() {
  int tc;
  scanf("%d", &tc);
  while (tc--) {
    solve();
  }
}
