#include <bits/stdc++.h>
using namespace std;
vector<pair<long long int, pair<long long int, long long int>>> adj[100005];
bool vis[100005];
long long int subtree[100005];
vector<long long int> sum1, sum2;
long long int n, s;
long long int fac_2(long long int x) {
  long long int cnt = 0;
  while (x) {
    x /= 2;
    if (x % 2 == 1) cnt++;
  }
  return cnt;
}
struct piiii {
  pair<long long int, long long int> a;
  pair<long long int, long long int> b;
  bool operator<(const piiii &p) const {
    if (a.first == p.a.first && b.first == p.b.first)
      return b.second < p.b.second;
    if (a.first == p.a.first) return b.first < p.b.first;
    return a.first < p.a.first;
  }
};
priority_queue<piiii> pq1, pq2;
void DFS(long long int x) {
  vis[x] = 1;
  subtree[x] = 0;
  bool flag = 1;
  for (auto i : adj[x]) {
    if (!vis[i.first]) {
      DFS(i.first);
      flag = 0;
      subtree[x] += subtree[i.first];
      long long int w = subtree[i.first] * i.second.first;
      long long int dif = w - (i.second.first / 2) * subtree[i.first];
      long long int cost = i.second.second;
      if (cost == 1)
        pq1.push({{dif, cost}, {subtree[i.first], i.second.first}});
      else
        pq2.push({{dif, cost}, {subtree[i.first], i.second.first}});
      if (cost == 1)
        sum1[0] += w;
      else
        sum2[0] += w;
    }
  }
  if (flag) subtree[x] = 1;
}
void clear_pq(priority_queue<piiii> &pq) {
  priority_queue<piiii> empty;
  swap(empty, pq);
}
void init() {
  clear_pq(pq1);
  clear_pq(pq2);
  sum1.clear(), sum2.clear();
  sum1.push_back(0);
  sum2.push_back(0);
  for (int i = 1; i <= n; i++) {
    vis[i] = 0;
    adj[i].clear();
  }
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%lld %lld", &n, &s);
    init();
    for (int i = 0; i < n - 1; i++) {
      long long int a, b, w, c;
      scanf("%lld %lld %lld %lld", &a, &b, &w, &c);
      adj[a].push_back({b, {w, c}});
      adj[b].push_back({a, {w, c}});
    }
    DFS(1);
    long long int ans = 0;
    while (sum1.back() > 0) {
      long long int cost = pq1.top().a.second;
      long long int dif = pq1.top().a.first;
      long long int sub = pq1.top().b.first;
      long long int edge = pq1.top().b.second / 2;
      long long int now = sub * edge;
      sum1.push_back(sum1.back() - dif);
      pq1.pop();
      long long int after = sub * (edge / 2);
      if (edge) pq1.push({{now - after, cost}, {sub, edge}});
    }
    while (sum2.back() > 0) {
      long long int cost = pq2.top().a.second;
      long long int dif = pq2.top().a.first;
      long long int sub = pq2.top().b.first;
      long long int edge = pq2.top().b.second / 2;
      long long int now = sub * edge;
      sum2.push_back(sum2.back() - dif);
      pq2.pop();
      long long int after = sub * (edge / 2);
      if (edge) pq2.push({{(now - after), cost}, {sub, edge}});
    }
    long long int mi = 0x3f3f3f3f;
    for (long long int i = 0; i < (long long int)sum1.size(); i++) {
      long long int l = -1, r = (long long int)sum2.size() - 1;
      while (l < r - 1) {
        long long int m = (l + r) / 2;
        if (sum1[i] + sum2[m] > s)
          l = m;
        else
          r = m;
      }
      if (sum1[i] + sum2[r] <= s) mi = min(mi, i + 2 * r);
    }
    printf("%lld\n", mi);
  }
  return 0;
}
