#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long t, n, m, s, a, b, w, c;
  cin >> t;
  while (t--) {
    cin >> n >> s;
    vector<vector<pair<long long, pair<long long, long long>>>> ady(n + 1);
    for (int i = 1; i < n; ++i) {
      cin >> a >> b >> w >> c;
      ady[a].push_back({b, {w, c}});
      ady[b].push_back({a, {w, c}});
    }
    int id = 0;
    long long sum = 0;
    vector<long long> cost(n + 1), sons(n + 1), color(n + 1);
    vector<bool> visited(n + 1);
    priority_queue<pair<long long, long long>> q;
    auto val = [&](long long c, long long v) { return v * c; };
    auto par = [&](long long idx) {
      return pair<long long, long long>(
          val(sons[idx], cost[idx]) - val(sons[idx], cost[idx] / 2), idx);
    };
    function<void(long long)> dfs = [&](long long v) {
      visited[v] = true;
      long long hojas = (ady[v].size() == 1 && v != 1);
      for (auto &x : ady[v]) {
        if (!visited[x.first]) {
          dfs(x.first);
          cost[id] = x.second.first;
          color[id] = x.second.second - 1;
          hojas += sons[id];
          sum += val(sons[id], cost[id]);
          q.push(par(id));
          ++id;
        }
      }
      sons[id] = hojas;
    };
    dfs(1);
    vector<vector<long long>> values(2);
    while (q.top().first != 0) {
      auto x = q.top();
      q.pop();
      values[color[x.second]].push_back(x.first);
      cost[x.second] = cost[x.second] / 2;
      q.push(par(x.second));
    }
    partial_sum(values[0].begin(), values[0].end(), values[0].begin());
    partial_sum(values[1].begin(), values[1].end(), values[1].begin());
    long long oo = (values[1].size() + values[0].size()) * 2ll;
    auto find = [&](long long val) {
      int idx = lower_bound(values[1].begin(), values[1].end(), val) -
                values[1].begin();
      if (idx == values[1].size()) return oo;
      return (idx + 1) * 2ll;
    };
    long long best = find(sum - s) * (sum > s);
    for (int i = 0; i < values[0].size(); ++i) {
      long long temp = (i + 1);
      long long d = sum - values[0][i];
      if (d > s) temp += find(d - s);
      best = min(best, temp);
    }
    cout << best << "\n";
  }
  return 0;
}
