#include<bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define LL long long 
#define mod 1000000007 
#define all(v) v.begin(),v.end()
#define pr(v) pair<v,v>
#define pb push_back
#define FOR(i, j, k) for (auto i=j ; i<k ; i++)
#define ROF(i, j, k) for (auto i=j ; i>=k ; i--) 

const long long INF = 1e18;
const long long MAX = 2e5+10;
int main() {
    fastio;
    int t=1; cin>>t;
    while (t--) {
        int n; cin>>n; int a[n][n];
        FOR(i, 0, n) FOR(j, 0, n) cin>>a[i][j];
        
        FOR(k, 0, n) {
            int i=k, j=0, p=n-1-k, q=p-i, temp;
            while (q-- && i<p) {
                temp=a[i][i];
                while (j<=p) {
                    swap(temp, a[j][i]);j++; 
                }j=i+1; 
                while (j<=p) {
                    swap(temp, a[p][j]);j++;
                }j=p-1;
                while (j>=i) {
                    swap(temp, a[j][p]); j--;
                }j=p-1;
                while (j>=i) {
                    swap(temp, a[i][j]); j--;
                }
                 j=i;          
            }
        }
        FOR(i,0,n) {
            FOR(j,0,n) cout<<a[i][j]<<" ";
            cout<<"\n";
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
 
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define LL long long 
#define mod 1000000007 
#define all(v) v.begin(),v.end()
#define FOR(i, j, k) for (auto i=j ; i<k ; i++)

const long long INF = 1e18;
const long long MAX = 2e5+10;
LL sum=0;
int dfs(int u, int p,vector<pair<LL,LL>>adj[],vector<int>&vis,priority_queue<pair<LL,LL>>&w,LL l){
    vis[u]=1; int cnt=0,le=0,tt;
    for(auto v : adj[u]) 
        if(!vis[v.first]){
            tt=dfs(v.first,u,adj,vis,w,l+v.second); 
            le+=tt; cnt++;
            w.push({v.second*tt,v.second});
        }
    if(cnt==0) {sum+=l; return 1; }
    return le;
}
int main(){
    fastio;
    int t=1; cin>>t;
    while(t--){
        LL n,s; cin>>n>>s;sum=0;
        vector<pair<LL,LL>>adj[n+1];  priority_queue<pair<LL,LL>>w; vector<int>vis(n+1,0);
        FOR(i,0,n-1){
            LL u,v,w; cin>>u>>v>>w;
            adj[u].push_back({v,w}); adj[v].push_back({u,w});
        }
        dfs(1,-1,adj,vis,w,0);
        int ans = 0; 
        while(sum>s && !w.empty()) {
            auto q = w.top(); w.pop();
            if(q.second) 
                sum-=q.first/2,w.push({q.first/2,q.second/2}),ans++;
        }
        cout<<ans<<"\n"; 
    }
}