#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5;
vector<tuple<int, long long, int>> g[maxn];
struct node {
  long long val;
  int cnt;
  bool operator<(const node& rhs) const {
    return (val - val / 2) * cnt > (rhs.val - rhs.val / 2) * rhs.cnt;
  }
};
multiset<node> ms;
multiset<node> ms2;
int dfs(int u, int par) {
  if (g[u].size() == 1 && u != 1) return 1;
  int cnt = 0;
  for (auto tp : g[u]) {
    int v = std::get<0>(tp);
    long long w = std::get<1>(tp);
    auto c = std::get<2>(tp);
    if (v == par) continue;
    int cur = dfs(v, u);
    if (c == 1) {
      ms.insert(node({w, cur}));
    } else {
      ms2.insert(node({w, cur}));
    }
    cnt += cur;
  }
  return cnt;
}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    long long S;
    cin >> n >> S;
    for (int i = 1; i <= n; i++) g[i].clear();
    for (int i = 1, u, v, w, c; i < n; i++) {
      cin >> u >> v >> w >> c;
      g[u].emplace_back(v, w, c);
      g[v].emplace_back(u, w, c);
    }
    ms.clear();
    ms2.clear();
    dfs(1, 0);
    long long sum = 0;
    for (auto [a, b] : ms) {
      sum += a * b;
    }
    for (auto [a, b] : ms2) {
      sum += a * b;
    }
    int res = 0;
    while (sum > S) {
      if (ms.empty()) {
        auto [a, b] = *ms2.begin();
        ms2.erase(ms2.begin());
        sum -= a * b;
        a /= 2;
        sum += a * b;
        ms2.insert(node({a, b}));
        res += 2;
      } else if (ms2.empty()) {
        auto [a, b] = *ms.begin();
        ms.erase(ms.begin());
        sum -= a * b;
        a /= 2;
        sum += a * b;
        ms.insert(node({a, b}));
        res++;
      } else {
        auto it = ms.begin();
        auto [a1, b1] = *it;
        long long sub1 = (a1 - a1 / 2) * b1;
        a1 /= 2;
        bool ffirst = ms.size() == 1;
        long long sub2 = (a1 - a1 / 2) * b1;
        if (!ffirst) {
          it++;
          auto [a2, b2] = *it;
          if (sub2 >= (a2 - a2 / 2) * b2) {
            ffirst = true;
          } else {
            sub2 = (a2 - a2 / 2) * b2;
          }
        }
        auto [a, b] = *ms2.begin();
        long long sub = (a - a / 2) * b;
        if (sum - sub1 <= S || sub1 + sub2 >= sub) {
          auto [a, b] = *ms.begin();
          ms.erase(ms.begin());
          sum -= a * b;
          a /= 2;
          sum += a * b;
          ms.insert(node({a, b}));
          res++;
        } else {
          auto [a, b] = *ms2.begin();
          ms2.erase(ms2.begin());
          sum -= a * b;
          a /= 2;
          sum += a * b;
          ms2.insert(node({a, b}));
          res += 2;
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}
