#include <bits/stdc++.h>
using namespace std;
std::vector<std::vector<pair<int, pair<int, int>>>> adj;
std::vector<bool> visited;
std::vector<int> leaves;
std::vector<int> edges;
priority_queue<pair<long long int, int>> pq1, pq2;
long long int ans;
void dfs(int x) {
  visited[x] = true;
  if (adj[x].size() == 1) leaves[x] = 1;
  for (auto& i : adj[x]) {
    if (visited[i.first] == false) {
      edges[i.first] = i.second.first;
      dfs(i.first);
      leaves[x] += leaves[i.first];
      ans += (long long int)leaves[i.first] * (long long int)i.second.first;
      long long int temp =
          (long long int)leaves[i.first] *
          ((long long int)i.second.first - (long long int)i.second.first / 2);
      if (i.second.second == 1)
        pq1.push(make_pair(temp, i.first));
      else
        pq2.push(make_pair(temp, i.first));
    }
  }
}
void solve() {
  int n;
  long long int s;
  cin >> n >> s;
  adj.assign(n, std::vector<pair<int, pair<int, int>>>(0));
  visited.assign(n, 0);
  leaves.assign(n, 0);
  edges.assign(n, 0);
  pq1 = priority_queue<pair<long long int, int>>();
  pq2 = priority_queue<pair<long long int, int>>();
  ans = 0;
  for (long long int i = 0; i < n - 1; i++) {
    int a, b, w, c;
    cin >> a >> b >> w >> c;
    adj[a - 1].push_back(make_pair(b - 1, make_pair(w, c)));
    adj[b - 1].push_back(make_pair(a - 1, make_pair(w, c)));
  }
  dfs(0);
  std::vector<long long int> val1, val2;
  long long int curr = 0;
  long long int tot = ans;
  val1.push_back(0), val2.push_back(0);
  while (ans > 0 && !pq1.empty()) {
    auto temp = pq1.top();
    ans -= temp.first;
    long long int edg = edges[temp.second];
    edg /= 2;
    edges[temp.second] = edg;
    long long int tmp =
        (long long int)leaves[temp.second] * (long long int)(edg - edg / 2);
    pq1.pop();
    if (tmp != 0) pq1.push(make_pair(tmp, temp.second));
    val1.push_back(temp.first);
    curr += temp.first;
  }
  while (ans > 0 && !pq2.empty()) {
    auto temp = pq2.top();
    ans -= temp.first;
    long long int edg = edges[temp.second];
    edg /= 2;
    edges[temp.second] = edg;
    long long int tmp =
        (long long int)leaves[temp.second] * (long long int)(edg - edg / 2);
    pq2.pop();
    if (tmp != 0) pq2.push(make_pair(tmp, temp.second));
    val2.push_back(temp.first);
  }
  int minmoves = INT_MAX;
  for (int i = 0; i < (int)val1.size() - 1; i++) {
    val1[i + 1] += val1[i];
  }
  for (int i = 0; i < (int)val2.size() - 1; i++) {
    val2[i + 1] += val2[i];
  }
  int j = (int)val2.size() - 1;
  for (int i = 0; i < (int)val1.size(); ++i) {
    while (j > -1 && val1[i] + val2[j] >= tot - s) {
      minmoves = min(minmoves, i + 2 * j);
      j--;
    }
  }
  cout << minmoves << "\n";
}
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  int ttt;
  cin >> ttt;
  while (ttt--) {
    solve();
  }
}
