#include <bits/stdc++.h>

using namespace std;

const int N = 2005; const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int n, d[N][N];

int pre[N], low[N], sccno[N], dfs_clock;
stack<int> stk; int scc_c;
inline void Tarjan(int u) {
    pre[u] = low[u] = ++dfs_clock; stk.push(u);
    for(int v = 1; 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_c ++;
        do {
            y = stk.top(); stk.pop(); sccno[y] = scc_c;
        } while(y != u);
    }
}

struct edge {
    int from, to, dist;
    edge(int u = 0, int v = 0, int d = 0) : from(u), to(v), dist(d) {}
};
int G[N][N];
int ind[N], outd[N];
inline void Build() {
    for(int i = 0; i <= n + 1; i ++)
        for(int j = 0; j <= n + 1; j ++)
            G[i][j] = -1;
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++) if(d[i][j] > 0) {
        G[i][j] = 0;
        if(sccno[i] != sccno[j]) G[j][i] = d[i][j], ind[sccno[j]] ++, outd[sccno[i]] ++;
    }
    pair<int, int> ans = {-1, -1};
    for(int i = 1; i <= scc_c; i ++) {
        if(!ind[i]) ans.first = i;
        if(!outd[i]) ans.second = i;
    }
    for(int i = 1; i <= n; i ++) if(sccno[i] == ans.second) G[0][i] = 0;
    for(int i = 1; i <= n; i ++) if(sccno[i] == ans.first) G[i][n + 1] = 0;
}

int prv[N]; long long dist[N]; bool vis[N];
inline void Dijkstra(int S) {
    dist[S] = 0;
    for(int i = 0; i < n + 2; i ++) {
        int u = -1;
        for(int j = 0; j <= n + 1; j ++) if(!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        vis[u] = true;
        for(int j = 0; j <= n + 1; j ++) 
            if(G[u][j] >= 0 && dist[j] > dist[u] + G[u][j]) {
                dist[j] = dist[u] + G[u][j];
                prv[j] = u;
            }
    }
}

inline void Init() {
    memset(pre + 1, 0, sizeof(int) * n);
    memset(low + 1, 0, sizeof(int) * n);
    memset(sccno + 1, 0, sizeof(int) * n);
    memset(ind + 1, 0, sizeof(int) * n), memset(outd + 1, 0, sizeof(int) * n);
    memset(dist, 0x3f, sizeof(long long) * (n + 2));
    memset(vis, false, sizeof(bool) * (n + 2));
    dfs_clock = scc_c = 0;
}

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

    int T; cin >> T;
    while(T --) {
        cin >> n; Init();
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                cin >> d[i][j];
        if(n == 2) {cout << "NO\n"; continue; }
        cout << "YES\n";
        for(int i = 1; i <= n; i ++) 
            if(!pre[i]) Tarjan(i);
        if(scc_c == 1) {cout << "0 0\n"; continue; }
        Build(); Dijkstra(0);

        vector<pair<int, int>> ans;
        int u = n + 1;
        while(u) {
            if(G[prv[u]][u] > 0) ans.push_back({u, prv[u]});
            u = prv[u];
        }
        cout << ans.size() << ' ' << dist[n + 1] << '\n';
        for(auto &pr : ans) cout << pr.first << ' ' << pr.second << '\n';
    }

    return 0;
}