#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct cmp {
  bool operator()(const pair<long long, long long> &p1,
                  const pair<long long, long long> &p2) {
    return p1.second < p2.second;
  }
};
const long long G = 100005;
long long a, K, o, eso;
vector<pair<long long, long long> > n[G];
long long wei[G], dp[G], c_lf[G], cost[G];
void stf(long long v, long long p) {
  dp[v] = cost[0] = 0;
  c_lf[v] = 0;
  long long cnt = 0;
  for (pair<long long, long long> h : n[v]) {
    if (h.first == p) continue;
    cnt++;
    wei[h.first] = h.second / 2;
    cost[h.first] = h.second % 2 + 1;
    stf(h.first, v);
    c_lf[v] += c_lf[h.first];
    dp[v] += dp[h.first] + c_lf[h.first] * wei[h.first];
  }
  c_lf[v] += cnt == 0;
}
int main() {
  cin.tie(0);
  cout.tie(0);
  cin.sync_with_stdio(0);
  cout.sync_with_stdio(0);
  ;
  long long z;
  cin >> z;
  for (; z--;) {
    cin >> a >> K;
    for (int q = 0; q < a - 1; q++) {
      long long x, y, w, c;
      cin >> x >> y >> w >> c;
      x--, y--;
      c--;
      n[x].push_back({y, w * 2 + c});
      n[y].push_back({x, w * 2 + c});
    }
    wei[0] = o = 0;
    stf(0, -1);
    eso = dp[0] - K;
    priority_queue<pair<long long, long long>,
                   vector<pair<long long, long long> >, cmp>
        PQ1, PQ2;
    for (int q = 1; q < a; q++) {
      if (cost[q] == 1)
        PQ1.push({q, c_lf[q] * (wei[q] - wei[q] / 2)});
      else
        PQ2.push({q, c_lf[q] * (wei[q] - wei[q] / 2)});
    }
    PQ1.push({0, 0});
    PQ1.push({0, 0});
    PQ2.push({0, 0});
    PQ2.push({0, 0});
    for (; eso > 0;) {
      pair<long long, long long> p = PQ1.top();
      PQ1.pop();
      long long num = p.first, cur = p.second;
      if (cur >= eso) {
        o++;
        break;
      }
      long long cur2 =
          max(PQ1.top().second, c_lf[num] * (wei[num] / 2 - wei[num] / 4));
      long long s2 = PQ2.top().second;
      if (cur + cur2 >= s2) {
        eso -= cur;
        wei[num] /= 2;
        PQ1.push({num, c_lf[num] * (wei[num] - wei[num] / 2)});
        o++;
      } else {
        PQ1.push(p);
        p = PQ2.top();
        PQ2.pop();
        num = p.first, cur = p.second;
        eso -= cur;
        wei[num] /= 2;
        PQ2.push({num, c_lf[num] * (wei[num] - wei[num] / 2)});
        o += 2;
      }
    }
    cout << o << "\n";
    for (int q = 0; q < a; q++) n[q].clear();
  }
}
