#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e3 + 7;
const int INF = 1e16 + 1337;
int to[N][N], pr[N], d[N];
bool used[N];

void solve() {
    int n;
    cin >> n;
    pair <int, int> bd = {0, 0}, sd = {INF, 0};
    for (int i = 0; i < n; i++) {
        int deg = 0;
        for (int j = 0; j < n; j++) {
            cin >> to[j][i];
            if (to[j][i] > 0)
                deg++;
        }

        bd = max(bd, make_pair(deg, i));
        sd = min(bd, make_pair(deg, i));
    }

    if (n == 2) {
        cout << "NO\n";
        return;
    }

    fill(d, d + n, INF);
    fill(used, used + n, false);
    int s = sd.second, e = bd.second;
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = 0, dn = INF;
        for (int v = 0; v < n; v++) {
            if (!used[v] && d[v] < dn) {
                u = v;
                dn = d[v];
            }
        }

        used[u] = true;
        for (int v = 0; v < n; v++) {
            if (d[v] > dn + to[u][v]) {
                d[v] = dn + to[u][v];
                pr[v] = u;
            }
        }
    }

    int u = e;
    vector <pair <int, int>> ans;
    while (u != sd.second) {
        if (to[pr[u]][u] != 0)
            ans.push_back({pr[u], u});
        u = pr[u];
    }

    cout << "YES\n" << ans.size() << " " << d[e] << "\n";
    for (auto& [u, v] : ans)
        cout << v + 1 << " " << u + 1 << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
}