#include <bits/stdc++.h>
using namespace std;
template <typename T1>
void print(vector<T1> V, int add = 0, int start = -1, int end = -1) {
  if (start < 0) start = 0;
  if (end < 0) end = V.size() - 1;
  for (int i = start; i <= end; i++) {
    cout << V[i] + add << ((i == end) ? "\n" : " ");
  }
}
template <typename T1>
T1 chmin(T1 &x, const T1 v) {
  return x = min(x, v);
}
template <typename T1>
T1 chmax(T1 &x, const T1 v) {
  return x = max(x, v);
}
int n, x, y, p;
long long s;
vector<pair<int, int> > T[100001];
long long sw1, sw2;
struct Wg {
  long long w, c;
  long long save() const {
    long long hw = w / 2;
    return w * c - hw * c;
  }
  bool operator<(const Wg &aW) const { return save() < aW.save(); }
  void print() const { cout << w << " " << c << " " << save() << "\n"; }
};
priority_queue<Wg> Q1;
priority_queue<Wg> Q2;
int dfs(int i, long long w, int f) {
  long long sl = 0;
  for (const auto &ni : T[i])
    if (ni.first != f) {
      sl += dfs(ni.first, ni.second, i);
    }
  if (sl == 0) sl++;
  if (w > 0) {
    Q1.push({w, sl});
    sw1 += w * sl;
  }
  if (w < 0) {
    Q2.push({(-w), sl});
    sw2 += (-w) * sl;
  }
  return sl;
}
void solve() {
  cin >> n >> s;
  for (int i = 0; i < n + 1; i++) T[i].clear();
  while (Q2.size() > 0) Q2.pop();
  while (Q1.size() > 0) Q1.pop();
  int t;
  for (int i = 0; i < n - 1; i++) {
    cin >> x >> y >> p >> t;
    x--;
    y--;
    if (t == 2) p = -p;
    T[x].push_back({y, p});
    T[y].push_back({x, p});
  }
  sw1 = sw2 = 0;
  dfs(0, 0, -1);
  vector<long long> S1, S2;
  S1.push_back(sw1);
  S2.push_back(sw2);
  while (Q1.size() > 0) {
    Wg wg = Q1.top();
    Q1.pop();
    sw1 -= wg.save();
    wg.w /= 2;
    if (wg.w > 0) Q1.push(wg);
    S1.push_back(sw1);
  }
  while (Q2.size() > 0) {
    Wg wg = Q2.top();
    Q2.pop();
    sw2 -= wg.save();
    wg.w /= 2;
    if (wg.w > 0) Q2.push(wg);
    S2.push_back(sw2);
  }
  assert(sw1 == 0);
  assert(sw2 == 0);
  long long ans = S1.size() + 2ll * S2.size();
  int j = 0;
  for (int i = S1.size() - 1; i >= 0; i--) {
    if (S1[i] > s) break;
    while (S1[i] + S2[j] > s) j++;
    ans = min(ans, 2ll * j + i);
  }
  {
    cout << ans << "\n";
    return;
  };
}
int main() {
  int test;
  cin >> test;
  while (test--) {
    solve();
  }
  return 0;
}
