#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream &operator<<(ostream &os, vector<T> V) {
  os << "[ ";
  for (auto v : V) os << v << " ";
  os << "]";
  return os;
}
template <class T>
ostream &operator<<(ostream &os, multiset<T> S) {
  os << "{ ";
  for (auto s : S) os << s << " ";
  return os << "}";
}
template <class L, class R>
ostream &operator<<(ostream &os, map<L, R> M) {
  os << "{ ";
  for (auto m : M) os << "(" << m.first << ":" << m.second << ") ";
  return os << "}";
}
template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
const long long N = 100005;
vector<pair<long long, pair<long long, long long>>> adj[N];
long long n, s, sum = 0;
multiset<pair<long long, pair<long long, long long>>> diff1, diff2;
long long calc(long long wt, long long leaves) {
  long long rem = wt - (wt / 2);
  rem *= leaves;
  return rem;
}
long long dfs(long long x, long long pr) {
  if (adj[x].size() == 1 && x != 1) return 1;
  long long k = 0;
  for (long long i = 0; i < adj[x].size(); i++) {
    if (adj[x][i].first != pr) {
      long long y = dfs(adj[x][i].first, x);
      if (adj[x][i].second.second == 1)
        diff1.insert(
            {calc(adj[x][i].second.first, y), {adj[x][i].second.first, y}});
      else
        diff2.insert(
            {calc(adj[x][i].second.first, y), {adj[x][i].second.first, y}});
      k += y;
      sum += adj[x][i].second.first * y;
    }
  }
  return k;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    sum = 0;
    long long x, y, w, c;
    cin >> n >> s;
    for (long long i = 1; i < n + 1; i++) adj[i].clear();
    for (long long i = 0; i < n - 1; i++)
      cin >> x >> y >> w >> c, adj[x].push_back({y, {w, c}}),
          adj[y].push_back({x, {w, c}});
    diff1.clear();
    diff2.clear();
    dfs(1, -1);
    long long ans = 0;
    while (sum > s) {
      pair<long long, pair<long long, long long>> p1 = {-1e18, {-1e18, -1e18}};
      pair<long long, pair<long long, long long>> p2 = {-1e18, {-1e18, -1e18}};
      if (!diff1.empty()) p1 = *(--diff1.end());
      if (!diff2.empty()) p2 = *(--diff2.end());
      if (p2.first == -1e18) {
        ans++;
        diff1.erase(--diff1.end());
        sum -= p1.first;
        long long newWt = p1.second.first / 2;
        if (newWt != 0)
          diff1.insert(
              {calc(newWt, p1.second.second), {newWt, p1.second.second}});
      } else if (p1.first == -1e18) {
        ans += 2;
        diff2.erase(--diff2.end());
        sum -= p2.first;
        long long newWt = p2.second.first / 2;
        if (newWt != 0)
          diff2.insert(
              {calc(newWt, p2.second.second), {newWt, p2.second.second}});
      } else if (sum - p1.first <= s) {
        ans++;
        break;
      } else if (diff1.size() == 1 &&
                 p2.first >
                     p1.first + calc(p1.second.first / 2, p1.second.second)) {
        ans += 2;
        diff2.erase(--diff2.end());
        sum -= p2.first;
        long long newWt = p2.second.first / 2;
        if (newWt != 0)
          diff2.insert(
              {calc(newWt, p2.second.second), {newWt, p2.second.second}});
      } else {
        long long tot = p1.first;
        if (diff1.size() > 1) {
          auto it = --(diff1.end());
          --it;
          tot += max(it->first, calc(p1.second.first / 2, p1.second.second));
        } else
          tot += calc(p1.second.first / 2, p1.second.second);
        if (tot >= p2.first) {
          diff1.erase(--diff1.end());
          sum -= p1.first;
          ans++;
          long long newWt = p1.second.first / 2;
          if (newWt != 0)
            diff1.insert(
                {calc(newWt, p1.second.second), {newWt, p1.second.second}});
        } else {
          ans += 2;
          sum -= p2.first;
          long long newWt = p2.second.first / 2;
          diff2.erase(--diff2.end());
          if (newWt != 0)
            diff2.insert(
                {calc(newWt, p2.second.second), {newWt, p2.second.second}});
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}
