#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=2e3+5;
constexpr int INF=1e9+1;
int d[maxn][maxn];
int n,dfn[maxn],low[maxn],tqm,tot,fa[maxn];bool vis[maxn];
stack<int> s;
int g[maxn][maxn];
void dfs(int p){
    dfn[p]=low[p]=++tqm;vis[p]=1;s.push(p);
    for(int i=1;i<=n;i++)if(d[p][i]) low[p]=min(low[p],dfn[i]?vis[i]?low[i]:low[p]:(dfs(i),low[i]));
    if(dfn[p]==low[p]){
        ++tot;
        while(!s.empty()){
            int pp=s.top();s.pop();
            fa[pp]=tot;
            if(pp==p) break;
        }
    }
}
long long dp[maxn];
int lst[maxn],to[maxn];
pair<int,int> sb[maxn][maxn];
inline void solve(){
    cin>>n;for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) cin>>d[i][j];
    for(int i=1;i<=n;i++) dfn[i]=low[i]=vis[i]=0;tqm=tot=0;while(!s.empty()) s.pop();
    for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
    for(int i=1;i<=tot;i++)for(int j=1;j<=tot;j++) g[i][j]=(i==j?0:INF);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)if(d[i][j]){
        int fi=fa[i],fj=fa[j];
        if(g[fi][fj]>d[i][j]){
            g[fi][fj]=d[i][j];
            sb[fi][fj]=make_pair(i,j);
        }
    }
    dp[1]=0;
    for(int i=2;i<=tot;i++){
        dp[i]=1e18;
        int curm=1;
        for(int j=1;j<i;j++){
            if(g[i][curm]>g[i][j]) curm=j;
            if(g[i][curm]<INF){
                if(dp[j]+g[i][curm]<dp[i]) dp[i]=dp[j]+g[i][curm],lst[i]=curm,to[i]=j;
            }
        }
    }
    vector<pair<int,int>> ans;
    int z=tot;
    while(z!=1){
        ans.emplace_back(sb[z][lst[z]]);
        z=to[z];
    }
    cout<<ans.size()<<' '<<dp[tot]<<'\n';
    for(auto x:ans) cout<<x.first<<' '<<x.second<<'\n';
}
int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
}