#include <bits/stdc++.h>
using namespace std;
double PI = acos(-1);
vector<int> adj[100005];
bool vis[100005];
map<pair<int, int>, long long> edge;
map<pair<int, int>, pair<long long, int>> weight;
long long mod = 1e9 + 7;
int n, k;
long long dfs(int node) {
  vis[node] = 1;
  long long ans = 1;
  for (auto v : adj[node]) {
    if (!vis[v]) {
      long long a = dfs(v);
      edge[{v, node}] = a;
      edge[{node, v}] = a;
      ans += a;
    }
  }
  if (ans > 1) ans--;
  return ans;
}
void clc() {
  for (int i = 0; i <= n; i++) {
    adj[i].clear();
    vis[i] = 0;
  }
  edge.clear();
  weight.clear();
}
void test_case() {
  long long sum = 0, ans = 1e8, s;
  cin >> n >> s;
  pair<int, int> arr[n];
  vector<long long> v1, v2;
  v1.push_back(0), v2.push_back(0);
  for (int i = 0; i < n - 1; i++) {
    int x, y, c, w;
    cin >> x >> y >> c >> w;
    adj[x].push_back(y), adj[y].push_back(x);
    arr[i] = {x, y};
    weight[{x, y}] = {c, w}, weight[{y, x}] = {c, w};
  }
  dfs(1);
  for (int i = 0; i < n; i++) {
    long long x = edge[{arr[i].first, arr[i].second}],
              y = weight[{arr[i].first, arr[i].second}].first;
    sum += x * y;
    while (y) {
      if (weight[{arr[i].first, arr[i].second}].second == 1)
        v1.push_back(x * y - x * (y / 2));
      else
        v2.push_back(x * y - x * (y / 2));
      y /= 2;
    }
  }
  sort(v1.begin() + 1, v1.end());
  sort(v2.begin() + 1, v2.end());
  reverse(v1.begin() + 1, v1.end());
  reverse(v2.begin() + 1, v2.end());
  for (int i = 1; i < v1.size(); i++) v1[i] += v1[i - 1];
  for (int i = 1; i < v2.size(); i++) v2[i] += v2[i - 1];
  for (int i = 0; i < v2.size(); i++) {
    long long pos =
        lower_bound(v1.begin(), v1.end(), sum - s - v2[i]) - v1.begin();
    if (pos == v1.size()) continue;
    ans = min(ans, pos + 2 * i);
  }
  cout << ans << '\n';
  clc();
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    test_case();
  }
  return 0;
}
