#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int t, n, cho[N];
long long S, w[N];
struct node {
  int ne, v, w, cho;
} edge[N << 1];
int head[N], tot;
void add(int x, int y, int w, int cho) {
  edge[++tot].v = y;
  edge[tot].w = w;
  edge[tot].cho = cho;
  edge[tot].ne = head[x];
  head[x] = tot;
}
int deg[N], sz[N];
void dfs(int son, int fa) {
  if (son != 1 && sz[son] == 1) deg[son] = 1;
  for (int i = head[son]; i; i = edge[i].ne) {
    int v = edge[i].v;
    if (v == fa) continue;
    w[v] = edge[i].w;
    cho[v] = edge[i].cho;
    dfs(v, son);
    deg[son] += deg[v];
  }
}
void init() {
  for (int i = 1; i <= n; i++) head[i] = deg[i] = sz[i] = cho[i] = 0;
  tot = 0;
}
int main() {
  scanf("%d", &t);
  while (t--) {
    init();
    scanf("%d %lld", &n, &S);
    for (int i = 1; i < n; i++) {
      int x, y, w, cho;
      scanf("%d %d %d %d", &x, &y, &w, &cho);
      add(x, y, w, cho);
      add(y, x, w, cho);
      sz[x]++;
      sz[y]++;
    }
    dfs(1, 0);
    long long sum = 0, cnt = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                   less<pair<long long, int> > >
        se1, se2;
    for (int i = 1; i <= n; i++) {
      long long tmp = 1LL * w[i] * deg[i];
      sum += tmp;
      if (cho[i] == 1)
        se1.push({(w[i] - w[i] / 2) * deg[i], i});
      else if (cho[i] == 2)
        se2.push({(w[i] - w[i] / 2) * deg[i], i});
    }
    vector<long long> v1, v2;
    v1.push_back(0);
    v2.push_back(0);
    while (true) {
      if (se1.size() == 0) break;
      auto it = se1.top();
      se1.pop();
      long long val = it.first;
      int p = it.second;
      if (val == 0) break;
      v1.push_back(val);
      w[p] /= 2;
      se1.push({(w[p] - w[p] / 2) * deg[p], p});
    }
    while (true) {
      if (se2.size() == 0) break;
      auto it = se2.top();
      se2.pop();
      long long val = it.first;
      int p = it.second;
      if (val == 0) break;
      v2.push_back(val);
      w[p] /= 2;
      se2.push({(w[p] - w[p] / 2) * deg[p], p});
    }
    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];
    long long mi = 1e18;
    for (int i = 0; i < v2.size(); i++) {
      long long tmp = sum - v2[i];
      long long res = tmp - S;
      int pos = lower_bound(v1.begin(), v1.end(), res) - v1.begin();
      if (pos >= (int)v1.size()) continue;
      mi = min(mi, 2LL * i + pos);
    }
    printf("%lld\n", mi);
  }
  return 0;
}
