#include <bits/stdc++.h>

using namespace std;

const int N = 2005;
int n, d[N][N];

int pre[N], low[N], dfs_clock;
int scc_siz, sccno[N]; stack<int> stk;

void Tarjan(int u) {
    pre[u] = low[u] = ++dfs_clock; stk.push(u);
    for(int i = 0; i < n; i ++) if(d[u][i]) {
        if(!pre[i]) {
            Tarjan(i); low[u] = min(low[u], low[i]);
        } else if(!sccno[i]) low[u] = min(low[u], pre[i]);
    }
    if(low[u] >= pre[u]) {
        ++scc_siz; int y;
        do {
            y = stk.top(); stk.pop(); sccno[y] = scc_siz;
        } while(y != u);
    }
}

int p[N];
int find(int x) {return x == p[x] ? x : p[x] = find(p[x]); }

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while(T --) { dfs_clock = scc_siz = 0;
        cin >> n;
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                cin >> d[i][j];
        memset(pre, 0, sizeof(int) * n);
        memset(low, 0, sizeof(int) * n);
        memset(sccno, 0, sizeof(int) * n);
        for(int i = 0; i < n; i ++)
            if(!pre[i]) Tarjan(i);
        
        for(int i = 0; i < n; i ++) p[sccno[i]] = sccno[i];
        typedef pair<int, pair<int, int>> node;
        vector<node> vec;
        for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++) 
            if(sccno[i] != sccno[j] && d[i][j])
                vec.push_back({d[i][j], {i, j}});
        sort(vec.begin(), vec.end());

        long long ans = 0;
        vector<pair<int, int>> res;
        for(auto &nd : vec) {
            int x = sccno[nd.second.first], y = sccno[nd.second.second];
            if(find(x) == find(y)) continue;
            p[find(x)] = find(y);
            ans += nd.first, res.push_back(nd.second);
        }
        cout << res.size() << ' ' << ans << '\n';
        for(auto &pr : res) cout << pr.first + 1 << ' ' << pr.second + 1 << '\n';
    }

    return 0;
}