(*   INPUT	: The associated datafile for PDM(Moore-Bellman)
		  algorithm is  called "MooreDatafile".
		  
		  The FIRST NUMBER in "MooreDatafile" is the # of 
		  nodes in a given network.

		  The SECOND NUMBER is the # of edges in a 
		  given network.

		  The rest of numbers in "MooreDatafile" are the edges
		  from node i(first number) to node j(second number)
		  with a given weight (third number).

	**	  The first number of each edge in"MooreDatafile" is
		  in non-decreasing order.

		  The representation of a network for this algorithm
		  is the FORWARD-STAR form of data structure.

     Algorithm	: The PDM(Moore-Bellman) algorithm  computes the shortest
		  distances from a given source node S(node 1) to all other
		  nodes in an N-node 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 can take on NEGATIVE weighted edges.

     OUTPUT	: Outputs of this program
		  1. Shortest distance from node 1 to every other nodes
		  2. Traced the nodes which shortest path take on from
		     S to a node in the network.

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


     NOTE	: If the network is large and sparse, and if shortest path
		  from source node S to all other nodes is needed,  
		  Then This PDM algorithm is preferred.
		  
		  If the network is small and dense, Dijkstra algorithm
		  is faster and preferred.                               *)
  		   





program Moore(input, output, MooreDatafile,MooreOutfile);

const   maxnode = 50;
        maxedge = 100;
        INF     = 200;

type    CHARFILE = file of char;
        ARRN = array[1..maxnode] of integer;
        ARRN1 = array[1..maxnode+1] of integer;
        ARRM = array[1..maxedge] of integer;

var     N,  S,  M, Nextint : integer;
        MooreDatafile      : CHARFILE;
	MooreOutfile	   : CHARFILE;
        POINTER            : ARRN1;
        ENDV,     WT       : ARRM;
        DIST,   PRED       : ARRN;


procedure Infile(var POINTER : ARRN1;
                 var ENDV    : ARRM;
                 var WT      : ARRM;
                 var N,  M   : integer;
                 var Nextint : integer  );

var counter,  i : integer;

begin (* Infile *)
  reset(MooreDatafile);
  readln(MooreDatafile, Nextint);
  N := Nextint;
  readln(MooreDatafile, Nextint);
  M := Nextint;
  i := 1;
  POINTER[1] := 1;
  for counter := 1 to M do
  begin
    read(MooreDatafile, Nextint);
    if i <> Nextint then
       POINTER[Nextint] := counter;
       i := Nextint;
    read(MooreDatafile, Nextint);
    ENDV[counter] := Nextint;
    readln(MooreDatafile, Nextint);
    WT[counter] := Nextint;
  end;
  POINTER[N+1] := M+1;
end; (* Infile *)


procedure PDM(
       N,S,INF:integer;
   var POINTER  :ARRN1;
   var ENDV,WT  :ARRM;
   var DIST,PRED:ARRN);

   var U,V,J,HEAD,FIRST,LAST,NEXT,NEWLABEL,TEMP:integer;
       QUEUE                                   :ARRN;
begin
   for V:=1 to N do begin
      DIST[V]:=INF;            (* INF = WEIGHT OF A NONEXISTING EDGE *)
      PRED[V]:=-1;  QUEUE[V]:=-1
   end;
   DIST[S]:=0;  HEAD:=S;  U:=S;
   QUEUE[HEAD]:=INF;                          (* INITIALIZATION OVER *)
   while U <> INF do begin
      NEXT:=QUEUE[U];  QUEUE[U]:=0;
      FIRST:=POINTER[U];  LAST:=POINTER[U+1]-1;
      for J:=FIRST to LAST do begin
         V:=ENDV[J];
         NEWLABEL:=DIST[U]+WT[J];
         if DIST[V] > NEWLABEL then begin            (* CHANGE LABEL *)
            PRED[V]:=U;  DIST[V]:=NEWLABEL;
            TEMP:=NEXT;
            if QUEUE[V] < 0 then begin
               QUEUE[HEAD]:=V;  HEAD:=V;  QUEUE[HEAD]:=INF;
               if TEMP = INF then TEMP:=V;
               NEXT:=TEMP
            end
            else
               if QUEUE[V] = 0 then begin
                  QUEUE[V]:=TEMP;  NEXT:=V
               end
               else  NEXT:=TEMP
         end (* IF DIST[V] > NEWLABEL *)
      end;  (* FOR J *)
      U:=NEXT
   end  (* WHILE U <> INF *)
end;  (* PDM *)



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

var counter : integer;

begin
  rewrite(MooreOutfile);
  writeln(MooreOutfile,'        NODE   DISTANCE     PREDECESSOR    ');
  for counter := 1 to N do
  begin
    write (MooreOutfile,counter);
    write (MooreOutfile,DIST[counter]);
    writeln (MooreOutfile,'   ',PRED[counter]);
  end;
end;



begin (* main *)
  S := 1;
  Infile(POINTER,ENDV,WT,N,M,Nextint);
  PDM(N,S,INF,POINTER,ENDV,WT,DIST,PRED);
  Outfile(DIST,N,PRED);
end.