#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
#define MAX 2020
#define MAXS 20
#define BMAX 35
#define MOD 998244353
#define INF 1'000'100'000'000'000
#define TC 1
#define ln '\n'
#define bb ' '
ll mp[MAX][MAX];
vector<int> adj[MAX];
stack<int> S;
int cnt;
int low[MAX], ord[MAX], vis[MAX];
int col[MAX];
vector<vector<int>> scc;
void dfs(int x) {
	low[x] = ord[x] = ++cnt;
	vis[x] = 1;
	S.push(x);
	for (auto v : adj[x]) {
		if (!ord[v]) {
			dfs(v);
			low[x] = min(low[x], low[v]);
		}
		else if (vis[v]) low[x] = min(low[x], ord[v]);
	}
	if (low[x] == ord[x]) {
		int t;
		vector<int> v;
		while (S.size()) {
			t = S.top();
			S.pop();
			v.push_back(t);
			col[t] = scc.size();
			vis[t] = 0;
			if (t == x) break;
		}
		scc.push_back(v);
	}
}
ll C[MAX][MAX];
pii mv[MAX][MAX];
ll dp[MAX];
int path[MAX];
void solve() {
	int N;
	cin >> N;
	int i, j;
	scc.clear();
	cnt = 0;
	S = stack<int>();
	for (i = 1; i <= N; i++) low[i] = ord[i] = vis[i] = col[i] = 0, adj[i].clear();
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			cin >> mp[i][j];
			if (mp[i][j]) adj[i].push_back(j);
		}
	}
	for (i = 1; i <= N; i++) if (!ord[i]) dfs(i);
	int S = scc.size();
	vector<int> sord;
	for (i = 0; i < S; i++) sord.push_back(i);
	sort(sord.begin(), sord.end(), [&](int i, int j) {return mp[scc[i][0]][scc[j][0]]; });
	for (i = 0; i < S; i++) {
		for (j = i + 1; j < S; j++) {
			C[i][j] = INF;
			for (auto u : scc[sord[i]]) for (auto v : scc[sord[j]]) {
				if (C[i][j] > mp[u][v]) {
					C[i][j] = mp[u][v];
					mv[i][j] = pii(u, v);
				}
			}
		}
	}
	int k;
	for (k = S - 1; k > 1; k--) {
		for (i = 0; i < S; i++) {
			j = i + k;
			if (j >= S) break;
			if (C[i + 1][j] > C[i][j]) {
				C[i + 1][j] = C[i][j];
				mv[i + 1][j] = mv[i][j];
			}
			if (C[i][j - 1] > C[i][j]) {
				C[i][j - 1] = C[i][j];
				mv[i][j - 1] = mv[i][j];
			}
		}
	}
	for (i = 1; i < S; i++) {
		dp[i] = C[0][i];
		path[i] = 0;
		for (j = 0; j < i; j++) {
			ll nv = dp[j] + C[j][i];
			if (dp[i] > nv) {
				dp[i] = nv;
				path[i] = j;
			}
		}
	}
	int v = S - 1;
	vector<int> pv;
	while (v) {
		pv.push_back(v);
		v = path[v];
	}
	reverse(pv.begin(), pv.end());
	int p = 0;
	cout << pv.size() << bb << dp[S - 1] << ln;
	for (auto v : pv) {
		auto& pi = mv[p][v];
		cout << pi.first << bb << pi.second << ln;
		p = v;
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	cin >> T;
	while (T--) solve();
}