(*   INPUT	: The associated datafile for Floyd algorithm is called
		  "FloydDatafile".

		  The FIRST NUMBER in FloydDatafile is the # of nodes in
		  a given network.

		  The rest of numbers are for WEIGHT MATRIX of a given
		  network.

		  The representation of a network for this algorithm is the
                  WEIGHT MATRIX.  The WEIGHT MATRIX of an n-node network is an
                  n X n matrix W=[wij] in which the (i,j)th entry wij is the
                  weight of (i,j), the edge from node i to node j.

     ALGORITHM	: The FLOYD algorithm computes shortest paths between all pairs
		  of nodes.

		  The FLOYD algorithm produces the shortest-distance matrix W
		  and the path matrix P in a given network with N nodes.  If
		  there is a negative cycle, the boolean variable NEGACYCLE
		  is set to TRUE.

		  Maximum # of nodes in a netwrok is set to be maxnode=50.
                  If N > 50.  One can change the setting of maxnode to an even
                  larger number that is > N.

                  Similarly, infinity(no edge between two given nodes) INF is
                  set to be 200.

     OUTPUT	: Outputs are
		  1.  Check whether or not there exist a negative cycle;
		  2.  Output shortest-distance  matrix from every node
		      to every other node.
		  3.  Path matrix with which actual shortest path from every
		      node to every other node.

     Time       : The running time is O(N^3) regardless of the density of a
		  given network.

		  The storage requirement is N^2 for storing the Weight Matrix 
	          and path matrix P                                 *) 



program ALLPAIR(input,output,FloydDatafile,FloydOutfile);

const INF = 200;
      maxnode = 50;

type  CHARFILE = file of char;
      ARRNN    = array[1..maxnode,1..maxnode] of integer;

var   N, Nextint : integer;
      NEGACYCLE  : boolean;
      W,  P      : ARRNN;
      FloydDatafile : CHARFILE;
      FloydOutfile  : CHARFILE;




procedure Infile(var W : ARRNN;
                 var N, Nextint : integer);

var row, column : integer;


begin
  reset(FloydDatafile);
  readln(FloydDatafile, Nextint);
  N := Nextint;
  for row := 1 to N do
  begin
    for column := 1 to N do
    begin
      read(FloydDatafile, Nextint);
      W[row, column] := Nextint;
    end;
    readln(FloydDatafile);
  end;
end;




procedure FLOYD(
       N,INF    :integer;
   var NEGACYCLE:boolean;
   var W,P      :ARRNN);

   var I,J,L,NEWLABEL:integer;
begin
   for I:=1 to N do
      for J:=1 to N do
         if W[I,J] <> INF then P[I,J]:=I
         else P[I,J]:=0;
   NEGACYCLE:=false;                          (* INITIALIZATION OVER *)
   L:=1;
   while (L <= N) and (not NEGACYCLE) do begin
      for I:=1 to N do begin
         if W[I,L] <> INF  then
            for J:=1 to N do
              if W[L,J] <> INF then begin
                 NEWLABEL:=W[I,L]+W[L,J];
                 if W[I,J] > NEWLABEL then begin
                    W[I,J]:=NEWLABEL;  P[I,J]:=P[L,J]
                 end
              end;  (* IF W[L,J] <> INF, FOR J *)
         NEGACYCLE:=NEGACYCLE or (W[I,I] < 0)
      end;  (* FOR I *)
      L:=L+1
   end  (* WHILE (L <= N) ... *)
end;  (* FLOYD *)




procedure Outfile(W  : ARRNN;
                  N  : integer);

var row, column : integer;
  

begin
  rewrite(FloydOutfile);
  writeln(FloydOutfile,'      NEGATIVECYCLE  =  ',NEGACYCLE);
  writeln(FloydOutfile);
  writeln(FloydOutfile,'Distance matrix for all pairs ');
  for row := 1 to N do
  begin
    for column := 1 to N do
    begin
      write (FloydOutfile,W[row,column]);
    end;
    writeln(FloydOutfile);
  end;
  writeln(FloydOutfile);
  writeln(FloydOutfile);
  writeln(FloydOutfile,'Predecessor matrix  ');
  for row := 1 to N do
  begin
    for column := 1 to N do
    begin
      write(FloydOutfile,P[row,column]);
    end;
    writeln(FloydOutfile);
  end;
end;




begin (* main *)
   Infile(W,N,Nextint);
   FLOYD(N,INF,NEGACYCLE,W,P);
   Outfile(W,N);
end.