#include <bits/stdc++.h>

using namespace std;

const int N = 2005; const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int n, d[N][N];
pair<int, pair<int, int>> G[N][N]; int c[N][N];

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

int pr[N], ind[N]; long long f[N], S[N];

inline void init() {
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            c[i][j] = 0, G[i][j] = {0, {0, 0}};
    for(int i = 0; i < n; i ++)
        ind[i] = pre[i] = low[i] = sccno[i] = pr[i] = f[i] = S[i] = 0;
    dfs_clock = scc_cnt = 0;
}

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

inline vector<int> Topo() {
    queue<int> Q; vector<int> ans;
    for(int i = 1; i <= scc_cnt; i ++)
        if(!ind[i]) Q.push(i);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop(); ans.emplace_back(u);
        for(int v = 1; v <= scc_cnt; v ++) if(c[u][v]) {
            if(!--ind[v]) Q.push(v);
        }
    }
    return ans;
}

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

    int T; cin >> T;
    while(T --) {
        cin >> n;
        init();
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                cin >> d[i][j];
        for(int i = 0; i < n; i ++) 
            if(!pre[i]) Tarjan(i);
        for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++) if(sccno[i] != sccno[j] && d[i][j]) {
            int x = sccno[i], y = sccno[j];
            c[x][y] ++;
            if(c[x][y] == 1) G[x][y] = {d[i][j], {i + 1, j + 1}};
            else G[x][y] = min(G[x][y], {d[i][j], {i + 1, j + 1}});
            ind[y] += (c[x][y] == 1);
        } 
        vector<int> P = Topo();
        for(int i = 1; i < scc_cnt; i ++) S[i] = S[i - 1] + G[P[i - 1]][P[i]].first;
        assert(P.size() == scc_cnt);
        
        if(scc_cnt == 1) {cout << "YES\n0 0\n"; continue; }
        for(int i = 1; i < scc_cnt; i ++) {
            int u = P[i];
            f[i] = INF;
            if(c[P[i - 1]][P[i]] >= 2) f[i] = min(f[i], f[i - 1] + G[P[i - 1]][P[i]].first);
            for(int j = 0; j < i - 1; j ++) {
                f[i] = min(f[i], f[j] + G[P[j]][P[i]].first);
                f[i] = min(f[i], f[j] + (S[i] - S[j]));
            }
        }
        if(f[scc_cnt - 1] == INF) {cout << "NO\n"; continue; }
        cout << "YES\n";
        vector<pair<int, int>> ans;
        for(int i = scc_cnt - 1; i; ) {
            if(c[P[i - 1]][P[i]] >= 2 && f[i - 1] + G[P[i - 1]][P[i]].first == f[i]) {
                ans.emplace_back(G[P[i - 1]][P[i]].second);
                i = i - 1; continue;
            }
            for(int j = 0; j < i - 1; j ++) {
                if(f[i] == f[j] + G[P[j]][P[i]].first) {
                    ans.emplace_back(G[P[j]][P[i]].second);
                    i = j; break;
                } else if(f[i] == f[j] + (S[i] - S[j])) {
                    for(int k = j + 1; k <= i; k ++)
                        ans.emplace_back(G[P[k - 1]][P[k]].second);
                    i = j; break;
                }
            }
        }
        cout << ans.size() << ' ' << f[scc_cnt - 1] << '\n';
        for(auto &pr : ans) cout << pr.first << ' ' << pr.second << '\n';
    }

    return 0;
}