#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int man = 2e5 + 10;
const long long mod = 1e9 + 7;
struct edge {
  int v;
  int w;
  int next;
} e[man << 1];
int head[man];
int cnt;
void init(int n) {
  memset(head, 0, sizeof(int) * (n + 5));
  cnt = 0;
}
void add(int u, int v, int w) {
  e[++cnt].next = head[u];
  e[cnt].v = v;
  e[cnt].w = w;
  head[u] = cnt;
}
int vis[man];
int dfs(int u, int fa) {
  int num = 0;
  int cnt = 0;
  for (int i = head[u]; i; i = e[i].next) {
    if (e[i].v == fa) continue;
    ++cnt;
    int tp = dfs(e[i].v, u);
    num += tp;
    vis[i] = tp;
  }
  if (!cnt) num++;
  return num;
}
struct node {
  long long w;
  int cnt, va;
  bool operator<(const node &a) const {
    return 1ll * (va / 2 + va % 2) * cnt < 1ll * (a.va / 2 + a.va % 2) * a.cnt;
  }
};
signed main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    long long s = 0;
    long long sum = 0;
    scanf("%d%lld", &n, &s);
    for (int i = 1; i < n; ++i) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      add(u, v, w);
      add(v, u, w);
    }
    dfs(1, 1);
    priority_queue<node> q;
    for (int i = 1; i <= cnt; ++i) {
      if (vis[i] == 0) continue;
      sum += 1ll * e[i].w * vis[i];
      q.push(node{1ll * e[i].w * vis[i], vis[i], e[i].w});
    }
    if (sum <= s) {
      cout << 0 << '\n';
    } else {
      int cnt = 0;
      while (q.size()) {
        node tp = q.top();
        q.pop();
        ++cnt;
        int tpva = tp.va / 2 + tp.va % 2;
        sum -= 1ll * tpva * tp.cnt;
        tp.va -= tpva;
        tp.w = 1ll * tp.cnt * tp.va;
        if (tp.va) q.push(tp);
        if (sum <= s) break;
      }
      cout << cnt << '\n';
    }
    memset(vis, 0, sizeof(int) * (cnt + 5));
    init(n);
  }
  return 0;
}
