#include <bits/stdc++.h>
constexpr auto Inf = 0X3F3F3F3F;
using namespace std;
namespace IO {
inline long long read() {
  long long o = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c > '/' && c < ':') {
    o = o * 10 + c - '0';
    c = getchar();
  }
  return o * f;
}
inline char recd() {
  char o;
  while ((o = getchar()) < '0' || o > '9')
    ;
  return o;
}
inline double reod() {
  double o = read(), f = 1;
  char c;
  while ((c = getchar()) > '/' && c < ':') o += (c - '0') / (f *= 10);
  return o;
}
}  // namespace IO
using namespace IO;
const int SIZE = 2E5 + 7, Mod = 1E9 + 7;
vector<pair<int, pair<long long, int> > > vec[SIZE];
long long TS = 0;
struct Node {
  long long w;
  int c, cost;
  Node(long long w, long long c, long long cost) : w(w), c(c), cost(cost){};
  bool operator<(const Node& Tmp) const {
    return (w - w / 2) * c < (Tmp.w - Tmp.w / 2) * Tmp.c;
  }
};
priority_queue<Node> oque, sque;
int DFS(int now, int F) {
  int son = 0;
  for (int pos = 0; pos < vec[now].size(); pos++) {
    int v = vec[now][pos].first;
    if (v != F) {
      int s = DFS(v, now);
      TS += s * vec[now][pos].second.first;
      son += s;
      if (vec[now][pos].second.second == 1)
        oque.push(
            Node(vec[now][pos].second.first, s, vec[now][pos].second.second));
      else
        sque.push(
            Node(vec[now][pos].second.first, s, vec[now][pos].second.second));
    }
  }
  return son == 0 ? 1 : son;
}
long long aw[int(2E6)], bw[int(2E6)];
int main() {
  int T = read();
  while (T--) {
    int N = read();
    long long S = read(), Tmp;
    for (int pos = 1, u, v, w, c; pos < N; pos++) {
      u = read(), v = read(), w = read(), c = read();
      vec[u].push_back({v, {w, c}});
      vec[v].push_back({u, {w, c}});
    }
    DFS(1, 0);
    int ans = Inf, aInd = 1, bInd = 1;
    long long d = TS - S;
    Tmp = d;
    while (Tmp > 0 && !oque.empty()) {
      Node now = oque.top();
      oque.pop();
      Tmp -= (now.w - now.w / 2) * now.c;
      aw[aInd] = aw[aInd - 1] + (now.w - now.w / 2) * now.c;
      aInd++, now.w /= 2;
      if (now.w) oque.push(now);
    }
    Tmp = d;
    while (Tmp > 0 && !sque.empty()) {
      Node now = sque.top();
      sque.pop();
      Tmp -= (now.w - now.w / 2) * now.c;
      bw[bInd] = bw[bInd - 1] + (now.w - now.w / 2) * now.c;
      bInd++, now.w /= 2;
      if (now.w) sque.push(now);
    }
    int L = 0, R = bInd - 1;
    while (L < aInd && R >= 0) {
      while (R >= 0 && aw[L] + bw[R] >= d) ans = min(ans, L + (R << 1)), R--;
      L++;
    }
    printf("%d\n", TS <= S ? 0 : ans);
    for (int pos = 1; pos <= N; pos++) vec[pos].clear();
    TS = 0;
    while (!oque.empty()) oque.pop();
    while (!sque.empty()) sque.pop();
  }
}
