#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug(T...);
}
struct fast_power {
  long long integer(long long n, long long e,
                    long long my_mod = 9223372036854775807LL) {
    long long ans = 1;
    while (e) {
      if (e & 1)
        ans = (ans * n) % my_mod, e--;
      else
        n = (n * n) % my_mod, e >>= 1;
    }
    return ans;
  }
  long long matrix(vector<vector<long long>> &n, long long e,
                   long long my_mod = 9223372036854775807LL);
};
struct euclidean {
  int gcdi(int a, int b) { return b ? gcdi(b, a % b) : a; }
  double gcdf(double a, double b, double accuracy) {
    return b <= accuracy ? a : gcdf(b, fmod(a, b), accuracy);
  }
};
const int INF = 0x3f3f3f3f;
const int maxn = 100000 + 5;
vector<int> G[maxn];
vector<long long> dist[maxn];
vector<long long> cost[maxn];
long long int leaves[maxn];
int getleaves(int n, int fa) {
  int num = 0;
  for (int i = 0; i < G[n].size(); i++)
    if (G[n][i] != fa) num += getleaves(G[n][i], n);
  if (!num) num = 1;
  return leaves[n] = num;
}
struct Node {
  long long int n, e, cost;
  bool operator<(const Node &rhs) const {
    return (n - n / 2) * e * rhs.cost < (rhs.n - rhs.n / 2) * rhs.e * cost;
  }
};
long long int sum;
priority_queue<Node> s;
void dfs(int n, int fa) {
  for (int i = 0; i < G[n].size(); i++)
    if (G[n][i] != fa)
      sum += dist[n][i] * leaves[G[n][i]],
          s.push((Node){dist[n][i], leaves[G[n][i]], cost[n][i]}),
          dfs(G[n][i], n);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    long long int n, S;
    cin >> n >> S;
    for (int i = 1; i <= n; i++) cost[i].clear(), G[i].clear(), dist[i].clear();
    memset(leaves, 0, sizeof(int) * (n + 2));
    int f1, f2, w, c;
    for (int i = 0; i < n - 1; i++) {
      cin >> f1 >> f2 >> w >> c;
      G[f1].push_back(f2), G[f2].push_back(f1);
      dist[f1].push_back(w), dist[f2].push_back(w);
      cost[f1].push_back(c), cost[f2].push_back(c);
    }
    getleaves(1, -1);
    sum = 0;
    dfs(1, -1);
    int ans = 0;
    long long int num2 = 0, ok = 0, num1 = 1LL << 60, ok2 = 0;
    while (sum > S) {
      Node x = s.top();
      s.pop();
      sum -= (x.n - x.n / 2) * x.e;
      s.push({x.n / 2, x.e, x.cost});
      ans += x.cost;
      if (x.cost == 2)
        ok = 1, num2 = (x.n - x.n / 2) * x.e;
      else
        ok2 = 1, num1 = min(num1, (x.n - x.n / 2) * x.e);
    }
    if (ok2) {
      if (sum + num1 <= S) ans--, sum += num1;
    }
    if (ok) {
      sum += num2;
      while (s.size()) {
        Node x = s.top();
        s.pop();
        if (x.cost == 1 && sum - (x.n - x.n / 2) * x.e <= S) {
          ans--;
          break;
        }
      }
    }
    while (s.size()) s.pop();
    cout << ans << endl;
  }
  return 0;
}
