(*  INPUT     : The associated datafile for Dijkstra's algorithm is called 
		"datafile".

		The FIRST NUMBER in "datafile" is the # of nodes in a 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 Dijkstra algorithm computes the shortest distance from
		a given SOURCE (S) node which is denoted by node 1 to 
		another destinatin node (T) which is denoted by the Nth node
		in an N-nonde network.

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

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

		This algorithm only takes non-negative weight edges
	
    OUTPUT    : Given "datafile", The Dijkstra outputs 
		1. LABEL = TRUE if each node is permanently labeled.
		2. Shortest distance from node S to node T
		3. Traced the nodes which shortest path take on from
		   S to T.  This is given in array PRED[1..N].

    Time      : The running time of this algorithm is O(N^2)               

    NOTE      : If the network is small and dense, this Dijkstra algorithm
		is faster and preferred.

		If the network is large and sparse, and if shortest path
		from source node S to all other nodes is needed, 
		Then PDM algorithm is preferred.                           *)




(*************************************************************************)
program dijk (input, output, datafile, DijkstraOutfile);

const   max = 50;
        INF = 200;

type    CHARFILE = file of char;
        ARRNN    = array[1..max,1..max] of integer;
        ARRN     = array[1..max] of integer;
        BOOLARRN = array[1..max] of boolean;

var     datafile : CHARFILE;
	DijkstraOutfile : CHARFILE;
        N, Nextint  : integer;
        S,  T    : integer;
        W : ARRNN;
        PATH : boolean;
        FINAL : BOOLARRN;
        DIST,PRED:ARRN;



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

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


procedure  DIJKSTRA(
       N,INF,S,T:integer;
   var W        :ARRNN;
   var PATH     :boolean;
   var FINAL    :BOOLARRN;
   var DIST,PRED:ARRN);

   var U,V,Y,RECENT,NEWLABEL,TEMP:integer;
begin
   for V:=1 to N do begin
      DIST[V]:=INF;  FINAL[V]:=false;  PRED[V]:=-1
   end;                       (* INF = WEIGHT OF A  NONEXISTENT EDGE *)
   DIST[S]:=0;  FINAL[S]:=true;
   PATH:=true;  RECENT:=S;                    (* INITIALIZATION OVER *)
   while not FINAL[T] do begin
      for V:=1 to N do                             (* FIND NEW LABEL *)
         if (W[RECENT,V] < INF) and (not FINAL[V]) then begin
            NEWLABEL:=DIST[RECENT]+W[RECENT,V];
            if NEWLABEL < DIST[V] then begin
               DIST[V]:=NEWLABEL;  PRED[V]:=RECENT
            end
         end;
      TEMP:=INF;
      for U:=1 to N do               (* FIND SMALLEST LABELED VERTEX *)
         if (not FINAL[U]) and (DIST[U] < TEMP) then begin
            Y:=U;  TEMP:=DIST[U]
         end;
      if TEMP < INF then begin                    (* THERE IS A PATH *)
         FINAL[Y]:=true;  RECENT:=Y
      end
      else begin                     (* THERE IS NO PATH FROM S TO T *)
         PATH:=false;  FINAL[T]:=true
      end
   end  (* WHILE NOT FINAL[T] *)
end;  (* DIJKSTRA *)


procedure Outfile(
                  N : integer;
                FINAL : BOOLARRN; 
                  DIST : ARRN;
                 PRED : ARRN);

var counter : integer;

begin
  rewrite(DijkstraOutfile);
  writeln(DijkstraOutfile,'        Node     Distance      Label     Predecessor');
  for counter := 1 to N do
  begin
    write (DijkstraOutfile,counter);
    write (DijkstraOutfile,DIST[counter]);
    write (DijkstraOutfile,'           ',FINAL[counter]);
    writeln(DijkstraOutfile,PRED[counter]);
  end;
  writeln(DijkstraOutfile);

end;

begin (* main *)
  S := 1;
  T := N;
  Infile(W,N,Nextint);
  DIJKSTRA(N,INF,S,T,W,PATH,FINAL,DIST,PRED);
  Outfile(N,FINAL,DIST,PRED);
end.