var a,way,b:array[1..100,1..100]of longint;
    min,i,j,k,n,m:longint;
procedure change(h,t:longint);
begin
    if way[h,t]<>0 then
     begin
      change(h,way[h,t]);
      change(way[h,t],t);
     end
     else
     begin
      a[t,h]:=-1*a[h,t];
      a[h,t]:=0;
     end;
end;
begin
    read(n);
    for i:=1 to n do
     for j:=1 to n do
      read(a[i,j]);
    b:=a;
    for k:=1 to n do
     for i:=1 to n do
      for j:=1 to n do
       if (a[i,k]<>0) and (a[k,j]<>0) then
        begin
         if (a[i,j]=0) or (a[i,j]>a[i,k]+a[k,j])
         then
          begin
          a[i,j]:=a[i,k]+a[k,j];
          way[i,j]:=k;
          end;
        end;
     inc(min,a[1,n]);
     a:=b;
     change(1,n);
    for k:=1 to n do
     for i:=1 to n do
      for j:=1 to n do
       if (a[i,k]<>0) and (a[k,j]<>0) then
        if (a[i,j]=0) or (a[i,j]>a[i,k]+a[k,j])
         then a[i,j]:=a[i,k]+a[k,j];
     inc(min,a[1,n]);
    write(min);
end.