program ChengShiGuiHua;
var
  way:array[0..100,0..100] of longint;
  path:array[0..100,0..100] of boolean;
  n,i,j,r,k,sum:longint;
 
begin
  assign(input,'cityroad.in');
  reset(input);
  assign(output,'cityroad.out');
  rewrite(output);
  readln(n);
  for i:=1 to n do
    for j:=1 to n do
    begin
      read(r);
      if r>=1 then
      begin
        way[i,j]:=r;
        path[i,j]:=true;
      end
      else
      begin
        way[i,j]:=10000000;
        path[i,j]:=false;
      end
    end;
  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if i<>j then
          if way[i,k]+way[k,j]<=way[i,j] then
          begin
            way[i,j]:=way[i,k]+way[k,j];
            if path[i,j] then
            begin
              path[i,j]:=false;
              path[j,i]:=false;
            end
          end;
  sum:=0;
  for i:=1 to n-1 do
    for j:=i+1 to n do
      if path[i,j]=true then
        sum:=sum+way[i,j];
  writeln(sum);
  for i:=1 to n do
  begin
    for j:=1 to n do
      if path[i,j]
        then write(1,' ')
        else write(0,' ');
    writeln;
  end;
  close(input);
  close(output);
end.