#include<stdio.h>
#include<math.h>
#include<iomanip.h>
#define max 54
#define max1 54
//using namespace std;

typedef struct nod{
               int info;
               nod*urm;
               }*PNOD,NOD;
PNOD l[2*max];

int c[max1][max1],f[max1][max1],d[max1],t[max1];
int cost[max1][max1];
int n;

void citire();
void add(int ,int );
int minimizeaza();
void solve();
void drum();
void afisare();
int bellman();
int main()
{
	  freopen("cc.in","r",stdin);
	  freopen("cc.out","w",stdout);

	  citire();
	  solve();
	  afisare();
	  return 0;
}
void citire()
{
     int i,j,x;
     scanf("%d",&n);

     for(i=1;i<=n;i++)
     {
		      for(j=1;j<=n;j++)
		      {
				       scanf("%d",&x);
				       add( i, j+n );
				       add( j+n, i );
				       c[i][j+n]=c[j+n][i]=1;
				       cost[i][j+n]=cost[j+n][i]=x;


		      }

     }
     for(i=1;i<=n;i++)
     {
		      add(0,i);
		      add(i,0);
		      c[0][i]=c[i][0]=1;
		      cost[0][i]=cost[i][0]=0;
     }
     for(i=n+1;i<=n+n;i++)
     {
			  add ( i, n+n+1 );
			  add( n+n+1 , i );
			  c[i][n+n+1]=c[n+n+1][i]=1;
			  cost[i][n+n+1]=cost[n+n+1][i]=0;
     }
    // for(PNOD p=l[n+n];p;p=p->urm)
     //printf("%d ",p->info);
}

void add(int i,int j)
{
     PNOD p=new NOD;
     p->info=j;
     p->urm=l[i];
     l[i]=p;

}

void solve()
{
            while(bellman())
            drum();
}
int bellman()
{
    int i;
    for(i=0;i<=n+n+1;i++)
    {
			 d[i]=2000;
			 t[i]=0;
    }
    d[0]=0;
    for(i=0;i<=n+n+1;i++)
    minimizeaza();
    if(d[n+n+1]==2000)
    return 0;
    return 1;
}
int minimizeaza()
{
    int i,j,ok;
    ok=0;
    for(i=0;i<=n+n+1;i++)
         for(PNOD p=l[i];p;p=p->urm)
         {
                  j=p->info;
                           if(c[i][j]>f[i][j])
                           if(d[j]>d[i]+cost[i][j])
			   {
                                                   d[j]=d[i]+cost[i][j];
                                                   t[j]=i;
                                                   if(j==n+n+1) return 1;
                                                   ok=1;
                           }
                           if(f[j][i])
                           {
                                      if(d[j]>d[i]-cost[i][j])
                                      {
                                                              d[j]=d[i]-cost[i][j];
                                                              t[j]=-i;
                                                              if(j==n+n+1) return 1;
                                                              ok=1;
                                      }
                           }
                  }
         return ok;
}
void drum()
{
     int i,j;
     i=n+n+1;
     while(i)
     {
	     j=abs(t[i]);
	     if(t[j]>=0) f[j][i]++;
	     else
			f[i][j]--;
	     i=j;
     }
}
void afisare()
{
     int i,j,sol=0;
     for(i=1;i<=n;i++)
     {
		      for(j=n+1;j<=n+n+1;j++)
		      if(f[i][j])
		      {
			 printf("%d %d\n",i,j-n);
			 sol+=cost[i][j];
		      }
     }
     printf("\n");
     printf("%d ",sol);
}