var w,d:array[1..100,1..100] of integer;
begin
  assign(input, 'city.in');
  assign(output,'city.out');
  reset(input); rewrite(output);
  readln(n);
  for i:=1 to n do begin
    for j:=1 to n do read(w[i,j]); readln;
  end;
  for i:=1 to n do for j:=1 to n do if w[i,j]>0 then d[i,j]:=1 else d[i,j]:=99999;
  for i:=1 to n do for j:=1 to n do if i<>j then begin
    flag:=0;
    for k:=1 to n do
      if (k<>j) and (i<>k) then
        if d[i,k]+d[k,j]<d[i,j] then
          if flag=0 then begin
            d[i,j]:=d[i,k]+d[k,j];
            w[i,j]:=w[i,k]+w[i,j];
            flag:=1;
          end
          else if w[i,k]+w[k,j]<w[i,j] then w[i,j]:=w[i,k]+w[k,j];
  end;