#include <bits/stdc++.h>
using namespace std;
long long const INF = 2147483647, R_INF = 23372036854775807, MOD = 1e9 + 7;
const long long N = 2e5 + 2;
struct m7d {
  long long val, dif, idx;
  bool operator<(const m7d &A) const { return dif < A.dif; }
};
vector<pair<long long, long long>> adj[N];
long long occ[N], edge[N];
bool cost[N];
long long dfs(long long cur, long long par, long long prev) {
  for (auto u : adj[cur]) {
    if (u.first != par) occ[prev] += dfs(u.first, cur, u.second);
  }
  if (adj[cur].size() == 1) occ[prev] = 1;
  return occ[prev];
}
void calc_dif(m7d cur, priority_queue<m7d> &pq) {
  long long new_val = cur.val - cur.dif;
  edge[cur.idx] /= 2;
  pq.push({new_val, new_val - edge[cur.idx] / 2 * occ[cur.idx], cur.idx});
}
void solve(priority_queue<m7d> &pq, vector<long long> &res) {
  long long sum = 0;
  res.push_back(0);
  while (!pq.empty()) {
    auto cur = pq.top();
    pq.pop();
    if (!cur.dif) continue;
    sum += cur.dif;
    res.push_back(sum);
    calc_dif(cur, pq);
  }
  res.push_back(R_INF);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long TC;
  cin >> TC;
  while (TC--) {
    long long n, s;
    cin >> n >> s;
    for (long long i = 1; i < n + 1; i++) adj[i].clear(), occ[i] = 0;
    for (long long i = 1; i < n; i++) {
      long long u, v, w, c;
      cin >> u >> v >> w >> c;
      cost[i] = c == 2;
      edge[i] = w;
      adj[u].push_back({v, i});
      adj[v].push_back({u, i});
    }
    dfs(1, 1, 0);
    priority_queue<m7d> pq1, pq2;
    long long sum = 0;
    for (long long i = 1; i < n; i++) {
      long long cur = edge[i] * occ[i];
      sum += cur;
      if (cost[i])
        pq2.push({cur, cur - edge[i] / 2 * occ[i], i});
      else
        pq1.push({cur, cur - edge[i] / 2 * occ[i], i});
    }
    vector<long long> res1, res2;
    solve(pq1, res1);
    solve(pq2, res2);
    long long j = 0, ans = INF;
    for (long long i = res1.size() - 2; i >= 0; i--) {
      while (sum - res1[i] - res2[j] > s) j++;
      if (j != res2.size() - 1) ans = min(ans, i + j * 2);
    }
    cout << ans << endl;
  }
}
