#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, mod = 1e9 + 7;
vector<vector<pair<int, int>>> adj;
vector<int> weight, pass, c;
vector<int> leafs;
void dfs(int u, int pa) {
  bool bo = 1;
  for (auto x : adj[u]) {
    if (x.first == pa) continue;
    bo = 0;
    dfs(x.first, u);
    pass[x.second] = leafs[x.first];
    leafs[u] += leafs[x.first];
  }
  if (bo) leafs[u] = 1;
}
int main() {
  int tc = 1;
  scanf("%d", &tc);
  for (int cn = 1; cn <= tc; cn++) {
    int n;
    scanf("%d", &n);
    long long s;
    scanf("%lld", &s);
    adj.clear();
    leafs.clear();
    weight.clear();
    pass.clear();
    c.clear();
    adj.resize(n + 1);
    weight.resize(n + 1);
    pass.resize(n + 1);
    c.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
      int u, v, w;
      scanf("%d%d%d%d", &u, &v, &w, &c[i]);
      adj[u].push_back({v, i});
      adj[v].push_back({u, i});
      weight[i] = w;
    }
    leafs.resize(n + 1, 0);
    dfs(1, 1);
    vector<long long> v[2];
    long long sum = 0;
    for (int i = 0; i < n - 1; i++) {
      sum += 1ll * pass[i] * weight[i];
      while (weight[i]) {
        v[c[i] - 1].push_back(1ll * pass[i] * (weight[i] - (weight[i] / 2)));
        weight[i] /= 2;
      }
    }
    sort(v[0].begin(), v[0].end(), greater<long long>());
    sort(v[1].begin(), v[1].end(), greater<long long>());
    for (int j = 0; j < 2; j++) {
      for (int i = 1; i < (int)v[j].size(); i++) v[j][i] += v[j][i - 1];
    }
    int ans = (1 << 30);
    for (int i = 0; i <= (int)v[0].size(); i++) {
      long long cur = 0;
      if (i) cur = v[0][i - 1];
      int l = 0, r = (int)v[1].size(), res = -1;
      while (l <= r) {
        int mid = (l + r) >> 1;
        bool ok = 0;
        if (!mid)
          ok = (sum - cur <= s);
        else
          ok = (sum - cur - v[1][mid - 1] <= s);
        if (ok) {
          res = mid;
          r = mid - 1;
        } else
          l = mid + 1;
      }
      if (res == -1) continue;
      ans = min(ans, i + 2 * res);
    }
    printf("%d\n", ans);
  }
  return 0;
}
