#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
vector<pair<int, int>> adj[MAXN];
long long sum;
int n;
int type[MAXN];
long long wt[MAXN];
int subtr[MAXN];
long long affect(int idx) {
  return (wt[idx] * subtr[idx]) - ((wt[idx] / 2) * subtr[idx]);
}
void dfs(int node, int p) {
  if (adj[node].size() == 1) subtr[p] = 1;
  for (auto u : adj[node]) {
    if (u.second == p) continue;
    dfs(u.first, u.second);
    if (p != -1) subtr[p] += subtr[u.second];
  }
}
void init() {
  for (int i = 0; i < (n); i++) {
    adj[i].clear();
    type[i] = 0;
    subtr[i] = 0;
  }
}
vector<long long> perform(int typ) {
  set<pair<long long, int>, greater<pair<long long, int>>> s;
  long long cs = 0;
  for (int i = 0; i < (n - 1); i++) {
    if (type[i] == typ) {
      s.insert({affect(i), i});
      cs += wt[i] * subtr[i];
    }
  }
  vector<long long> res = {cs};
  while (cs > 0 && !s.empty()) {
    auto ele = *s.begin();
    s.erase(s.begin());
    cs -= affect(ele.second);
    wt[ele.second] /= 2;
    s.insert({affect(ele.second), ele.second});
    res.push_back(cs);
  }
  return res;
}
void solve() {
  cin >> n >> sum;
  init();
  for (int i = 0; i < (n - 1); i++) {
    int u, v;
    cin >> u >> v >> wt[i] >> type[i];
    --u;
    --v;
    adj[u].push_back(make_pair(v, i));
    adj[v].push_back(make_pair(u, i));
  }
  dfs(0, -1);
  vector<long long> v1 = perform(1), v2 = perform(2);
  int ans = 1e8;
  int ptr = (int)v2.size() - 1;
  for (int i = 0; i < (v1.size()); i++) {
    while (ptr > 0 && v2[ptr - 1] + v1[i] <= sum) --ptr;
    if (v1[i] + v2[ptr] <= sum) ans = min(ans, i + ptr * 2);
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
}
