#include <bits/stdc++.h>

using namespace std;

#define int long long
#define f first
#define s second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

using pii = pair <int, int>;

const int INF = 1e16 + 1337;
const int N = 2e3 + 7;

vector <pii> g[N], ng[N];
int pr[N], in[N], c[N];
bool used[N];
int n;

int get(int u) {
    if (pr[u] == u)
        return u;

    return pr[u] = get(pr[u]);
}

void mrg(int r1, int r2) {
    if (r1 == r2)
        return;

    if (c[r1] < c[r2])
        swap(r1, r2);

    pr[r2] = r1;
    in[r1] += in[r2];
    c[r1] += c[r2];
}

void dfs(int u) {
    used[u] = true;
    pr[u] = u;
    in[u] = 1;
    c[u] = 1;

    for (auto& [w, v] : g[u]) {
        if (!used[v])
            dfs(v);

        int r = get(v);
        if (in[r])
            mrg(get(u), r);
    }

    int r = get(u);
    in[r]--;
}

void clr() {
    for (int u = 0; u < n; u++) {
        g[u].clear();
        ng[u].clear();
        used[u] = false;
    }
}

void solve() {
    cin >> n;
    int d[n][n];
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            cin >> d[u][v];
            if (d[u][v] == 0)
                continue;

            g[u].pb({d[u][v], v});
        }
    }

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

    for (int u = 0; u < n; u++) {
        if (used[u])
            continue;

        dfs(u);
    }

    set <int> rt;
    for (int u = 0; u < n; u++)
        rt.insert(get(u));

    for (int u = 0; u < n; u++) {
        for (auto& [w, v] : g[u]) {
            int ru = get(u), rv = get(v);
            if (ru == rv)
                continue;

            if (rt.find(ru) != rt.end())
                rt.erase(ru);
        }
    }
    assert(sz(rt) == 1);
    int s = *rt.begin();

    rt.clear();
    for (int u = 0; u < n; u++)
        rt.insert(get(u));

    for (int u = 0; u < n; u++) {
        for (auto& [w, v] : g[u]) {
            int ru = get(u), rv = get(v);
            if (ru == rv)
                continue;

            if (rt.find(rv) != rt.end())
                rt.erase(rv);
        }
    }
    assert(sz(rt) == 1);
    int e = *rt.begin();

    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            int ru = get(u), rv = get(v);
//            if (u == 0 && v == 2) {
//                cout << ru << " " << rv << " " << d[u][v] << "|||||||\n";
//            }
            if (ru == rv)
                ng[v].pb({0, u});
            else if (d[u][v])
                ng[v].pb({d[u][v], u});
        }
    }

//    cout << s << " " << e << "|\n";
    int dp[n], pr[n];
    fill(dp, dp + n, INF);
    fill(pr, pr + n, -1);
    set <pii> st = {{0, s}};
    dp[s] = 0;
//    for (auto& [w, v] : ng[0])
//        cout << w << " " << v << "hete\n";
    while (!st.empty()) {
        int wn = st.begin()->f, u = st.begin()->s;
        st.erase(st.begin());

        if (dp[u] < wn)
            continue;

        for (auto& [w, v] : ng[u]) {
//            if (u == 0) {
//                cout << wn << " " << w << " " << v << "||\n";
//            }
            if (wn + w < dp[v]) {
                dp[v] = wn + w;
                pr[v] = u;
                st.insert({dp[v], v});
            }
        }
    }

    vector <int> path;
    int u = e;
    while (u != -1) {
        path.pb(u);
        u = pr[u];
    }
//    for (auto& x : path)
//        cout << x + 1 << " ";
//    cout << "\n\n";
//    reverse(all(path));

    vector <pii> ans;
    for (int i = 0; i < sz(path) - 1; i++) {
        assert(path[i] != path[i + 1]);
        if (get(path[i]) != get(path[i + 1]))
            ans.pb({path[i], path[i + 1]});
    }

//    assert(dp[e] != INF);
    cout << "YES\n" << sz(ans) << " " << dp[e] << "\n";
    for (auto& [u, v] : ans)
        cout << u + 1 << " " << v + 1 << "\n";
//    cout << "\n";
}

//1
//4
//0 5 0 2
//0 0 8 2
//2 0 0 1
//0 0 0 0

//1
//3
//0 10 3
//0 0 2
//0 0 0

//1
//3
//0 1 2
//0 0 0
//0 2 0

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