{$q+,r+,s+,i+,o-}
{$APPTYPE CONSOLE}
{
  Задача: matrix (венгерский алгоритм)
  Решение: Петр Калинин
  ЛКШ 2009.Август
}
uses SysUtils;
const inf=2000000000;
      maxn=250;
var gr:array[1..maxn,1..maxn] of integer;
    n:integer;
    f:text;
    pair1,pair2:array[1..maxn] of integer;
    was1,was2:array[1..maxn] of integer;
    from:array[1..maxn] of integer;
    w1,w2:array[1..maxn] of integer;
    min,minj:integer;
    next:integer;
    i,j:integer;
    ans:integer;
    nn,mm:integer;

function curgr(i,j:integer):integer;
begin
  result:=gr[i,j]+w1[i]+w2[j];
end;

function dist(j:integer):integer;
begin
if from[j]=0 then
   dist:=inf
else dist:=curgr(from[j],j);
end;

procedure go(j:integer);
var k:integer;
begin
was1[j]:=1;
for k:=1 to n do
    if (was2[k]=0)and(curgr(j,k)<dist(k)) then
       from[k]:=j;
end;

procedure check_pair(i,j:integer);
begin
  if (i=0)or(j=0) then exit;
  assert(curgr(i,j)=0,'Non-zero pairs');
end;

procedure docheck;
var i,j:integer;
begin
  for i:=1 to n do
      for j:=1 to n do
          assert(curgr(i,j)>=0,'Non-positive edges');
  for i:=1 to n do begin
      check_pair(i,pair1[i]);
      check_pair(pair2[i],i);
  end;
end;

begin
fillchar(w1,sizeof(w1),0);
fillchar(w2,sizeof(w2),0);
assign(f,'matrix.in');reset(f);
read(f,n);
for i:=1 to n do
    for j:=1 to n do begin
        read(f,gr[i,j]);
        if gr[i,j]+w1[i]<0 then w1[i]:=-gr[i,j];
    end;
//docheck;
close(f);
fillchar(pair1,sizeof(pair1),0);
fillchar(pair2,sizeof(pair2),0);
for i:=1 to n do begin
    fillchar(was1,sizeof(was1),0);
    fillchar(was2,sizeof(was2),0);
    fillchar(from,sizeof(from),0);
    for j:=1 to n do if pair1[j]=0 then
        go(j);
    nn:=0;
    while true do begin
          min:=inf;
          minj:=-1;
          for j:=1 to n do
              if (was2[j]=0) and (dist(j)<min) then begin
                 min:=dist(j);
                 minj:=j;
              end;
          for j:=1 to n do begin
              if was1[j]=1 then
                 w1[j]:=w1[j]-min;
              if was2[j]=1 then
                 w2[j]:=w2[j]+min;
          end;
//          docheck;
          was2[minj]:=1;
          if pair2[minj]=0 then break;
          go(pair2[minj]);
    end;
    while minj<>0 do begin
          next:=pair1[from[minj]];
          pair1[from[minj]]:=minj;
          pair2[minj]:=from[minj];
          minj:=next;
    end;
    docheck;
end;
assign(f,'matrix.out');rewrite(f);
ans:=0;
for i:=1 to n do
    ans:=ans+w1[i]+w2[i];
writeln(f,-ans);
for i:=1 to n do
    writeln(f,i,' ',pair1[i]);
close(f);
end.