#include <bits/stdc++.h>
#define int long long
#define elif else if
#define pb push_back

using namespace std;
vector<vector<int>> adj;

set<int> black_list;

long long bfs(int s, int en, set<int> &path){

    int n = adj.size();

    vector<bool> visited(n+1, false);
    vector<int> dist(n+1, 0);
    deque<int> q;

    visited[s] = 1;
    q.push_back(s);

    while(!q.empty()){
        int v = q.front();
        q.pop_front();
        for(auto u: adj[v]){
            if(visited[u]) continue;
            visited[u] = 1;
            dist[u] = dist[v] + 1;
            q.push_back(u);
        }
    }
    for(int x: dist) cout << x << " ";
    cout << endl;
    return dist[en];
}

void solve(){
    int n; cin >> n;

    vector<pair<pair<int, int>, int>> bb;
    map<int, int> aa;
    for(int i = 0; i < n; i++){
        int a, b, c; cin >> a >> b >> c;
        bb.push_back({{a, b}, c});
    }
    set<int> path;
    for(int i = 0; i < n; i++){
        int x1 = bb[i].first.first;
        int x2 = bb[i].first.second;
        adj.push_back({x1, x2});
        adj.push_back({x2, x1});
    }
    int mx = 0;
    set<int> ans;
    int anss = 0;
    for(int i = 1; i <= n; i++){
        bfs(1, n, path);
    }
    cout << anss << endl;



}

signed main()
{
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}
