#include <bits/stdc++.h>
using namespace std;
template <class A, class B>
ostream& operator<<(ostream& out, const pair<A, B>& a) {
  return out << "(" << a.first << ", " << a.second << ")";
}
template <class A>
ostream& operator<<(ostream& out, const vector<A>& v) {
  out << "[";
  for (int i = 0; i < v.size(); i++) {
    if (i) out << ", ";
    out << v[i];
  }
  return out << "]";
}
bool Check(int n, int pos) { return (bool)(n & (1 << pos)); }
struct edg {
  long long to, w, c;
};
vector<edg> g[100005];
vector<long long> v1, v2;
int vis[100005];
long long sum, s;
void calc(long long ws, long long lf, long long c) {
  while (ws) {
    long long wy = ws;
    ws /= 2LL;
    wy = wy - ws;
    if (c == 1)
      v1.emplace_back(wy * lf);
    else
      v2.emplace_back(wy * lf);
  }
}
long long dfs(long long i, long long ws) {
  vis[i] = 1;
  long long ret = 0;
  bool is_leaf = true;
  for (auto j : g[i]) {
    if (vis[j.to] == -1) {
      is_leaf = false;
      int r = dfs(j.to, ws + j.w);
      ret += r;
      calc(j.w, r, j.c);
    }
  }
  if (is_leaf) {
    sum += ws;
    return 1LL;
  }
  return ret;
}
void solve() {
  int n;
  cin >> n >> s;
  for (int i = 1; i < n; 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});
  }
  memset(vis, -1, sizeof(vis));
  dfs(0, 0);
  sort(v1.begin(), v1.end(), greater<long long>());
  sort(v2.begin(), v2.end(), greater<long long>());
  int len1 = v1.size();
  int len2 = v2.size();
  long long res = 0;
  int i = -1, j = 0;
  while (sum > s && i + 1 < len1) {
    res++;
    i++;
    sum -= v1[i];
  }
  while (sum > s && j < len2) {
    res += 2;
    sum -= v2[j];
    j++;
  }
  long long cur = res;
  while (i >= 0) {
    sum += v1[i];
    cur--;
    i--;
    while (sum > s && j < len2) {
      sum -= v2[j];
      cur += 2;
      j++;
    }
    if (sum <= s) {
      res = min(res, cur);
    }
  }
  cout << res << '\n';
  for (int i = 0; i <= n; i++) g[i].clear();
  v1.clear();
  v2.clear();
  sum = 0;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int q = 1;
  cin >> q;
  for (int kase = 1; kase <= q; kase++) {
    solve();
  }
  return 0;
}
