const MaxN=301;

var G:array [1..MaxN, 1..MaxN] of integer;
    u, v, B, D, X:array [0..MaxN] of integer;
    F:array [0..MaxN] of boolean;
    i, j, k, l, m, mj, n, t:integer;

begin
  reset (input, 'matrix.in');
  rewrite (output, 'matrix.out');
  read (n);
  for i:=1 to n do
    for j:=1 to n do
      read (G[i, j]);

  for i:=1 to n do begin
    fillchar (X, sizeof (X), 63);
    fillchar (F, sizeof (F), 0);
    l:=0; B[0]:=i;
    repeat
      F[l]:=true; k:=B[l]; m:=maxint; mj:=-1;
      for j:=1 to n do if not F[j] then begin
        t:=G[k, j]-u[k]-v[j];
        if (t<X[j]) then begin X[j]:=t; D[j]:=l end;
        if (X[j]<m) then begin m:=X[j]; mj:=j; end;
      end;
      for j:=0 to n do if F[j] then begin
        inc (u[B[j]], m); dec (v[j], m);
      end else dec (X[j], m);
      l:=mj; 
    until B[l]=0;
    repeat
      t:=D[l]; B[l]:=B[t]; l:=t;
    until l=0;
  end;

  writeln (-v[0]);
  for i:=1 to n do writeln (B[i], ' ', i);
end.