#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[2010][2010],n,d[2010],be[2010];
ll dp[2010];int dl[2010],pk[2010];
ll me[2010];int pl[2010];
int ds[2010];
void sol(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)d[i]=0,be[i]=i;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        scanf("%d",&a[i][j]);
        if(i!=j&&!a[i][j])d[i]++;
    }
    if(n==1){puts("YES"),puts("0 0");return;}
    if(n==2){puts("NO");return;}
    sort(be+1,be+n+1,[&](int x,int y){return d[x]<d[y];});
    for(int i=0;i<=n;i++)dp[i]=me[i]=1e18;
    dp[0]=0;
    for(int i=1,dg=0;i<=n;i++){
        dg+=d[be[i]];
        if(i==n||dg!=i*(i-1)/2){
            if(dp[i]>dp[i-1])dp[i]=dp[i-1],dl[i]=0;
        }
        for(int j=i+1;j<=n;j++)if(a[be[i]][be[j]]&&me[j]>a[be[i]][be[j]])
        me[j]=a[be[i]][be[j]],pl[j]=i;
        for(int j=i+1;j<=n;j++)if(dp[j-1]>dp[i-1]+me[j])dp[j-1]=dp[i-1]+me[j],dl[j-1]=pl[j],pk[j-1]=i-1;
    }
    int u=n;
    vector<pair<int,int> >xx;
    while(u){
        if(!dl[u])u--;
        else xx.push_back({be[dl[u]],be[u+1]}),u=pk[u];
    }
    printf("%d %lld\n",xx.size(),dp[n]);
    for(auto o:xx)printf("%d %d\n",o.first,o.second);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}