#include <bits/stdc++.h>
using namespace std;
list<pair<long long, long long>> adjList[(long long)(2e5 + 10)];
priority_queue<pair<long long, pair<long long, long long>>> pq;
long long s;
long long dfs(long long nd, long long par) {
  if (nd != 1 and adjList[nd].size() == 1) return 1;
  long long tot = 0;
  for (auto it : adjList[nd]) {
    if (it.first != par) {
      long long m = dfs(it.first, nd);
      pq.push({m * (it.second - it.second / 2), {it.second, m}});
      tot += m, s += m * it.second;
    }
  }
  return tot;
}
void solve() {
  s = 0;
  long long n, k;
  cin >> n >> k;
  for (long long i = 0; i < n - 1; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    adjList[a].push_back({b, c});
    adjList[b].push_back({a, c});
  }
  dfs(1, 0);
  long long cnt = 0;
  while (s > k) {
    long long e = pq.top().second.first;
    long long m = pq.top().second.second;
    pq.pop();
    s -= m * (e - (e / 2));
    cnt++;
    e /= 2;
    pq.push({m * (e - e / 2), {e, m}});
  }
  while (!pq.empty()) pq.pop();
  for (long long i = 1; i <= n; i++) adjList[i].clear();
  cout << cnt << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr), cin.tie(nullptr);
  long long t_c = 1;
  cin >> t_c;
  while (t_c--) solve();
}
