#include <bits/stdc++.h>
using namespace std;
void solve() {
  int n;
  long long S;
  cin >> n >> S;
  struct adj {
    int v, w, c;
  };
  vector<vector<adj>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v, w, c;
    cin >> u >> v >> w >> c;
    --u;
    --v;
    g[u].push_back({v, w, c});
    g[v].push_back({u, w, c});
  }
  vector<long long> len[2];
  long long tot = 0;
  function<int(int, int)> dfs = [&](int u, int p) {
    if (g[u].size() == 1 && u != 0) {
      return 1;
    }
    int sum = 0;
    for (auto [v, w, c] : g[u])
      if (v != p) {
        int leaves = dfs(v, u);
        tot += 1LL * leaves * w;
        while (w) {
          len[c - 1].push_back(1LL * (w + 1) / 2 * leaves);
          w /= 2;
        }
        sum += leaves;
      }
    return sum;
  };
  dfs(0, -1);
  tot = max(0LL, tot - S);
  int ans = (tot ? numeric_limits<int>::max() : 0);
  for (int i = 0; i < 2; ++i) {
    sort(len[i].rbegin(), len[i].rend());
    for (int j = 0; j < len[i].size(); ++j) {
      if (j) len[i][j] += len[i][j - 1];
      if (len[i][j] >= tot) {
        ans = min(ans, (i + 1) * (j + 1));
      }
    }
  }
  for (int i = 0; i < len[1].size(); ++i) {
    int j = lower_bound(len[0].begin(), len[0].end(), tot - len[1][i]) -
            len[0].begin();
    int cost = 2 * (i + 1) + (j + 1);
    if (j < len[0].size()) ans = min(ans, cost);
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    solve();
  }
}
