#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const double err = 1e-12;
const double PI = 3.141592653589793;
const int N = 1e5 + 5;
int n;
long long mxsm;
vector<vector<pair<int, int>>> adj;
vector<int> leaves;
vector<bool> vis;
map<pair<int, int>, int> cnt;
map<pair<int, int>, int> wgt;
map<pair<int, int>, int> cost;
int dfs(int v) {
  vis[v] = 1;
  for (auto i : adj[v]) {
    if (!vis[i.first]) {
      int tmp = dfs(i.first);
      leaves[v] += tmp;
      cnt[{v, i.first}] = tmp;
      wgt[{v, i.first}] = i.second;
    }
  }
  return leaves[v] = max(leaves[v], 1);
}
vector<long long> calc(int val) {
  vector<long long> ret;
  priority_queue<pair<long long, pair<int, int>>> pq;
  long long tmpsm = 0;
  for (auto i : cnt) {
    if (cost[i.first] == val) {
      long long c = cnt[i.first], w = wgt[i.first];
      tmpsm += c * w;
      long long dif = c * w - c * (w / 2);
      pq.push({dif, i.first});
    }
  }
  ret.push_back(tmpsm);
  while (tmpsm >= 1) {
    auto p = pq.top();
    pq.pop();
    tmpsm -= p.first;
    wgt[p.second] /= 2;
    long long c = cnt[p.second], w = wgt[p.second];
    long long dif = c * w - c * (w / 2);
    pq.push({dif, p.second});
    ret.push_back(tmpsm);
  }
  return ret;
}
void solve() {
  cin >> n >> mxsm;
  adj = vector<vector<pair<int, int>>>(n);
  leaves = vector<int>(n, 0);
  cnt.clear();
  wgt.clear();
  cost.clear();
  for (int i = 0; i < n - 1; i++) {
    int u, v, w, c;
    cin >> u >> v >> w >> c;
    --u, --v;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
    cost[{u, v}] = c;
    cost[{v, u}] = c;
  }
  vis = vector<bool>(n, 0);
  dfs(0);
  vector<long long> C1 = calc(1), C2 = calc(2);
  long long moves = 2e9;
  int l = 0, r = C2.size() - 1;
  for (int i = 0; i < C1.size(); i++) {
    while (r >= 0 && C1[i] + C2[r] <= mxsm) {
      moves = min(moves, (long long)i + 2ll * (long long)r);
      r--;
    }
  }
  cout << moves << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}
