#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int MAXM = 2e6 + 10;
const long long MOD = 1e9 + 7;
const long long INF = 0x3f3f3f3f;
const unsigned long long BASE = 233;
const int base = 5;
char rubbish[110];
bool GETDATA;
inline long long read() {
  long long x = 0, f = 1;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = -1;
  } while (ch < '0' || ch > '9');
  do {
    x = x * 10 + ch - 48;
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return x * f;
}
inline void write(long long x, char con = '\n') {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10, 0);
  putchar(x % 10 + '0');
  if (con) {
    printf("%c", con);
  }
}
struct edge {
  int to, nxt;
  long long val;
  int cost;
} es[MAXM];
int tot;
int head[MAXN];
void addedge(int u, int v, long long val, int cost) {
  es[tot] = edge{v, head[u], val, cost};
  head[u] = tot++;
}
void add(int u, int v, long long val, int cost) {
  addedge(u, v, val, cost);
  addedge(v, u, val, cost);
}
long long N, M, K;
vector<long long> ans[3];
long long sum[3][MAXM];
long long dist;
int dfs(int u, int fa) {
  int v;
  int res = 0;
  int now;
  long long val;
  bool leaf = true;
  for (int i = head[u]; ~i; i = es[i].nxt) {
    v = es[i].to;
    val = es[i].val;
    if (v == fa) {
      continue;
    }
    leaf = false;
    now = dfs(v, u);
    dist += val * now;
    res += now;
    while (val) {
      ans[es[i].cost].push_back((val - val / 2) * now);
      val /= 2;
    }
  }
  return res + leaf;
}
void init() {
  for (int i = 1; i <= N; i++) {
    head[i] = -1;
  }
  tot = 0;
  ans[1].clear();
  ans[2].clear();
  dist = 0;
}
void solve() {
  int res = INF;
  int now;
  int u, v, cost;
  long long val;
  N = read();
  M = read();
  init();
  for (int i = 1; i < N; i++) {
    u = read();
    v = read();
    val = read();
    cost = read();
    add(u, v, val, cost);
  }
  dfs(1, 1);
  sort(ans[1].begin(), ans[1].end(), greater<long long>());
  sort(ans[2].begin(), ans[2].end(), greater<long long>());
  for (int i = 1; i < 3; i++) {
    sum[i][0] = 0;
    for (int j = 0; j < ans[i].size(); j++) {
      sum[i][j + 1] = sum[i][j] + ans[i][j];
    }
  }
  dist -= M;
  for (int i = 0; i <= ans[2].size(); i++) {
    now = lower_bound(sum[1], sum[1] + 1 + ans[1].size(), dist - sum[2][i]) -
          sum[1];
    if (now == ans[1].size() + 1) {
      continue;
    }
    res = min(res, 2 * i + now);
  }
  write(res);
}
int main() {
  int T;
  T = 1;
  T = read();
  for (int t = 1; t <= T; t++) {
    GETDATA = false;
    solve();
  }
  return 0;
}
