#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> p)
{
    out << "(" << p.first << "," << p.second << ")";
    return out;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> v)
{
    out << "[";
    if (!v.empty())
        cout << v[0];
    for (int i = 1; i < (int)v.size(); i++)
        out << "," << v[i];
    out << "]";
    return out;
}
typedef long long ll;
const ll inf = 1e18;
int gmin(ll &x, ll y)
{
    if (y < x)
    {
        x = y;
        return 1;
    }
    return 0;
}
struct info
{
    int x, p, q;
};
void solve()
{
    int n;
    cin >> n;
    vector<vector<pair<int, ll>>> ve(n + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            ll x;
            cin >> x;
            if (x > 0)
                ve[i].emplace_back(j, x);
        }
    }
    if (n == 1)
    {
        cout << "YES\n0 0\n";
        return;
    }
    if (n == 2)
    {
        cout << "NO\n";
        return;
    }
    stack<int> s;
    int num = 0, dfstime = 0;
    vector<int> col(n + 1), dfn(n + 1), low(n + 1);
    auto tarjan = [&](auto &self, int u) -> void
    {
        s.push(u);
        dfn[u] = low[u] = ++dfstime;
        for (auto [v, len] : ve[u])
        {
            if (!dfn[v])
            {
                self(self, v);
                low[u] = min(low[u], low[v]);
            }
            else if (!col[v])
                low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u])
        {
            col[u] = ++num;
            while (s.top() != u)
            {
                col[s.top()] = num;
                s.pop();
            }
            s.pop();
        }
    };
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(tarjan, i);
    vector<vector<pair<int, ll>>> ve2(num + 1);
    vector<vector<tuple<int, ll, int, int>>> ve3(num + 1);
    vector<int> cnt(num + 1);
    for (int i = 1; i <= n; i++)
    {
        for (auto &[to, len] : ve[i])
            if (col[i] != col[to])
            {
                ve2[col[i]].emplace_back(col[to], len);
                ve3[col[to]].emplace_back(col[i], len, i, to);
                cnt[col[to]]++;
            }
    }
    vector<int> lis{0};
    {
        queue<int> qu;
        for (int i = 1; i <= num; i++)
            if (cnt[i] == 0)
                qu.push(i);
        while (!qu.empty())
        {
            int x = qu.front();
            qu.pop();
            lis.push_back(x);
            for (auto &[to, len] : ve2[x])
            {
                if (--cnt[to] == 0)
                    qu.push(to);
            }
        }
    }
    assert((int)lis.size() == num + 1);
    vector<int> id(num + 1);
    for (int i = 1; i <= num; i++)
        id[lis[i]] = i;
    vector<ll> dp(num + 1, inf);
    vector<info> pr(num + 1);
    vector<vector<pair<ll, int>>> mi(num + 1, vector<pair<ll, int>>(num + 1, make_pair(inf, 0)));
    dp[1] = 0;
    mi[1][1] = make_pair(0, 1);
    // cout << "col =" << col << endl;
    // cout << "lis =" << lis << endl;
    for (int i = 2; i <= num; i++)
    {
        for (auto [to, len, p, q] : ve3[lis[i]])
        {
            to = id[to];
            // cout << "i=" << i << " to=" << to << " len=" << len << " p=" << p << " q=" << q << endl;
            // cout << "v=" << mi[to][i - 1].first + len << endl;
            if (gmin(dp[i], mi[to][i - 1].first + len))
            {
                pr[i] = info{mi[to][i - 1].second, p, q};
            }
        }
        mi[i][i] = {dp[i], i};
        for (int j = i - 1; j >= 1; j--)
            mi[j][i] = min(mi[j][i - 1], mi[j + 1][i]);
    }
    int now = num;
    vector<pair<int, int>> ans;
    while (now != 1)
    {
        ans.emplace_back(pr[now].p, pr[now].q);
        now = pr[now].x;
    }
    cout << "YES\n";
    cout << ans.size() << " " << dp[num] << "\n";
    reverse(ans.begin(), ans.end());
    for (auto [x, y] : ans)
        cout << x << " " << y << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
}