#include <bits/stdc++.h>
using namespace std;
const long long N = 1000005;
struct edge {
  long long v, w, c;
};
vector<edge> g[N];
long long vis[N], d[N], c[N], w[N], n, m, s, sum, ans;
struct Item {
  long long w, d;
  long long op1() const { return (w - w / 2) * d; }
  long long op2() const { return (w - w / 2 / 2) * d; }
  bool operator<(const Item &b) const { return op1() < b.op1(); }
};
priority_queue<Item> que[3];
void clear() {
  for (long long i = 1; i <= n; i++) {
    g[i].clear();
    vis[i] = d[i] = c[i] = w[i] = 0;
  }
  while (que[1].size()) que[1].pop();
  while (que[2].size()) que[2].pop();
  sum = ans = 0;
}
void dfs(long long p) {
  vis[p] = 1;
  long long flag = 0;
  for (edge e : g[p]) {
    long long q = e.v;
    if (!vis[q]) {
      flag = 1;
      c[q] = e.c;
      w[q] = e.w;
      dfs(q);
      d[p] += d[q];
    }
  }
  if (flag == 0) d[p] = 1;
}
void solve() {
  cin >> n >> s;
  for (long long i = 1; i < n; i++) {
    long long t1, t2, t3, t4;
    cin >> t1 >> t2 >> t3 >> t4;
    g[t1].push_back({t2, t3, t4});
    g[t2].push_back({t1, t3, t4});
  }
  dfs(1);
  for (long long i = 2; i <= n; i++) {
    que[c[i]].push({w[i], d[i]});
    sum += w[i] * d[i];
  }
  while (sum > s) {
    if (que[1].size()) {
      long long tt = que[1].top().op1();
      if (sum - tt <= s) {
        ans++;
        break;
      }
    }
    long long t1 = 0, t2 = 0, t3 = 0;
    if (que[1].size()) t1 = que[1].top().op2();
    if (que[1].size() > 1) {
      auto tmp = que[1].top();
      t2 = que[1].top().op1();
      que[1].pop();
      t2 += que[1].top().op1();
      que[1].push(tmp);
    }
    if (que[2].size()) t3 = que[2].top().op1();
    if (t1 >= t2 && t1 >= t3) {
      auto tmp1 = que[1].top();
      sum -= tmp1.op1();
      que[1].pop();
      tmp1.w /= 2;
      que[1].push(tmp1);
      ans += 1;
    } else if (t2 >= t1 && t2 >= t3) {
      auto tmp1 = que[1].top();
      sum -= tmp1.op1();
      que[1].pop();
      tmp1.w /= 2;
      que[1].push(tmp1);
      ans += 1;
    } else {
      auto tmp = que[2].top();
      sum -= tmp.op1();
      que[2].pop();
      tmp.w /= 2;
      que[2].push(tmp);
      ans += 2;
    }
  }
  cout << ans << endl;
  clear();
}
signed main() {
  ios::sync_with_stdio(false);
  long long t;
  cin >> t;
  while (t--) {
    solve();
  }
}
