# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int du[2010],id[2010],d[2010][2010],pre[2010],g[2010][2010],dfn[2010],low[2010],sz[2010],inscc[2010],tot,scc_tot;
ll dis[2010];
bool vis[2010];
vector<int> G[2010],G2[2010];
stack<int> stk;
queue<int> que;
void tarjan(int u)
{
	dfn[u]=low[u]=++tot;
	stk.push(u);
	for(int v:G[u])
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(!inscc[v]) low[u]=min(low[u],dfn[v]);
	if(dfn[u]==low[u])
	{
		int w;scc_tot++;
		do
		{
			w=stk.top();stk.pop();
			sz[scc_tot]++;
			inscc[w]=scc_tot;
		}while(w!=u);
	}
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&d[i][j]);
		if(n==1){puts("YES\n0 0");continue;}
		if(n==2){puts("NO");continue;}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(d[i][j]>0) G[i].push_back(j);
		tot=scc_tot=0;
		for(int i=1;i<=n;i++)
			if(!dfn[i]) tarjan(i);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(d[i][j]>0 && inscc[i]!=inscc[j])
					du[inscc[j]]++,G2[inscc[i]].push_back(inscc[j]);
		int st=0,ed=0,cnt=0;
		for(int i=1;i<=scc_tot;i++)
			if(!du[i]) que.push(i),st=i;
		while(!que.empty())
		{
			int u=que.front();que.pop();
			ed=u;id[u]=++cnt;
			for(int v:G2[u])
				if(!(--du[v])) que.push(v);
		}
		for(int i=0;i<=n+1;i++)
			for(int j=0;j<=n+1;j++)
				g[i][j]=1e9;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(d[i][j]>0)
				{
					g[i][j]=0;
					if(inscc[i]==inscc[j]) continue;
					g[j][i]=d[i][j];
				}
		for(int i=1;i<=n;i++)
		{
			if(inscc[i]==ed) g[0][i]=0;
			if(inscc[i]==st) g[i][n+1]=0;
		}
		for(int i=1;i<=n+1;i++) dis[i]=1e18,vis[i]=0;
		dis[0]=0;vis[0]=0;
		for(int i=1;i<=n+2;i++)
		{
			int u=-1;
			for(int j=0;j<=n+1;j++)
				if(!vis[j] && (u<0 || dis[j]<=dis[u])) u=j;
			assert(u>=0);vis[u]=1;
			if(u==n+1) break;
			for(int v=0;v<=n+1;v++)
				if(dis[v]>dis[u]+g[u][v])
					dis[v]=dis[u]+g[u][v],pre[v]=u;
		}
		if(dis[n+1]>=1e18) puts("NO");
		else
		{
			puts("YES");
			int l=0;
			for(int u=n+1;u;u=pre[u]) l++;
			printf("%d %lld\n",l-2,dis[n+1]);
			for(int u=n+1;u;u=pre[u])
			{
				int v=pre[u];
				if(g[v][u]>0) printf("%d %d\n",u,v);
			}
		}
		for(int i=1;i<=n;i++) dfn[i]=low[i]=inscc[i]=0,G[i].clear();
		for(int i=1;i<=scc_tot;i++) sz[i]=du[i]=0,G2[i].clear();
	}
	return 0;
}