(*   INPUT	: The associated datafile for Kruskal algorithm is called
		  "KruskalDatafile".

		  The FIRST NUMBER in "KruskalDatafile" is the # of nodes
		  in a network.

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

	 	  Rest of data is based on the LIST of EDGES.
		  Edge from node i(first number) to node j(second number)
		  with a given weight(third number)

    Algorithm	: The Kruskal algorithm produces a minimum spanning tree
		  in a given undirected network with N nodes and M edges,
		  if network is not disconnected.

		  Maximum # of nodes in anetwork is set to be maxnode= 50.
		  If N > 50, one can modify to a larger number so that
	          maxnode > N.

		  Similarly, maximum # od edges is set to be maxedge=100.
		  One can modify (in const section of the program) so that
		  maxedge > M of a given network.

    OUTPUT	: Outputs are
		  1. Check whether the network is connected.
	          2. Tree edges in the minimum spanning tree(MST).
		  3. Total weight of tree edges in MST.

    NOTE	: Kruskal algorithm runs faster for large sparse graphs
		  (N >100).
		  
		  Since Kruskal algorithm depends on edges, the running 
		  time increses as the number of edges is increased.

		  Prim algorithm is preferred if graphs are small (N<100).

	                                                           *)

		  
		  
			 

program MST(input,output,KruskalDatafile,KruskalOutfile);

const   maxnode = 50;
        maxedge = 100;

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,  N1,   M   :  integer;
        ENDV1,   ENDV2  : ARRM;
        KruskalDatafile : CHARFILE;
	KruskalOutfile  : CHARFILE;
        CONNECT  :   boolean;
        TEDGE1,    TEDGE2  : ARRN1;
        WEIGHT   :   ARRM;
        TWEIGHT  :   integer;
        Nextint  : integer;



procedure  Infile ( var  N,  M  : integer;
                    var  ENDV1,  ENDV2 : ARRM;
                    var  WEIGHT : ARRM;
                    var Nextint : integer);

var counter : integer;

begin
  reset(KruskalDatafile);
  readln(KruskalDatafile, Nextint);
  N := Nextint;
  readln (KruskalDatafile,Nextint);
  M := Nextint;
  for counter := 1 to M do
  begin
    read(KruskalDatafile,Nextint);
    ENDV1[counter] := Nextint;
    read(KruskalDatafile,Nextint);
    ENDV2[counter] := Nextint;
    readln(KruskalDatafile, Nextint);
    WEIGHT[counter] := Nextint;
  end;
end;





procedure KRUSKAL(
       N,M               :integer;
   var ENDV1,ENDV2,WEIGHT:ARRM;
   var CONNECT           :boolean;
   var TEDGE1,TEDGE2     :ARRN1;
   var TWEIGHT           :integer);

   var I,LAST,U,V,R1,R2,ECOUNT,TCOUNT:integer;
       FATHER                        :ARRN;

   procedure HEAP(FIRST,LAST:integer);
      var J,K,TEMP1,TEMP2,TEMP3:integer;
   begin
      J:=FIRST;
      while J <= trunc(LAST/2) do begin
         if (2*J < LAST) and (WEIGHT[2*J+1] < WEIGHT[2*J]) then
            K:=2*J+1
         else K:=2*J;
         if WEIGHT[K] < WEIGHT[J] then begin
            TEMP1:=ENDV1[J];  TEMP2:=ENDV2[J];  TEMP3:=WEIGHT[J];
            ENDV1[J]:=ENDV1[K];  ENDV2[J]:=ENDV2[K];
            WEIGHT[J]:=WEIGHT[K];
            ENDV1[K]:=TEMP1;  ENDV2[K]:=TEMP2;
            WEIGHT[K]:=TEMP3;
            J:=K
         end  (* IF WEIGHT[K] < WEIGHT[J] *) 
         else J:=LAST
      end  (* WHILE J <= trunc(LAST/2) *)
   end;  (* HEAP *)

   function FIND(I:integer):integer;
     var PTR:integer;
   begin
      PTR:=I;
      while FATHER[PTR] > 0 do PTR:= FATHER[PTR];
      FIND:=PTR
   end;  (* FIND *)

   procedure UNION(I,J:integer);
      var X:integer;
   begin
      X:=FATHER[I]+FATHER[J];
      if FATHER[I] > FATHER[J] then begin
         FATHER[I]:=J;  FATHER[J]:=X
      end
      else begin
         FATHER[J]:=I;  FATHER[I]:=X
      end
   end;  (* UNION *)

begin                                                  (* MAIN BODY *)
   for I:=1 to N do FATHER[I]:=-1;
   for I:=trunc(M/2) downto 1 do                     (* INITIAL HEAP *)
      HEAP(I,M);
   LAST:=M;
   ECOUNT:=0;  TCOUNT:=0;
   TWEIGHT:=0;  CONNECT:=true;                (* INITIALIZATION OVER *)
   while ((TCOUNT < N-1) and (ECOUNT < M)) do begin
      ECOUNT:=ECOUNT+1;
      U:=ENDV1[1];  V:=ENDV2[1];
      R1:=FIND(U);  R2:=FIND(V);
      if R1 <> R2 then begin                 (* INCLUDE (U,V) IN MST *)
         TCOUNT:=TCOUNT+1;  UNION(R1,R2);
         TEDGE1[TCOUNT]:=U;  TEDGE2[TCOUNT]:=V;
         TWEIGHT:=TWEIGHT+WEIGHT[1]
      end;  (* IF R1 <> R2 *)
      ENDV1[1]:=ENDV1[LAST];  ENDV2[1]:=ENDV2[LAST];
      WEIGHT[1]:=WEIGHT[LAST];
      LAST:=LAST-1;
      HEAP(1,LAST)
   end;  (* WHILE ((TCOUNT < N-1) ... - ITERATION *)
   if TCOUNT <> N-1 then CONNECT:=false
end;  (* KRUSKAL *)


procedure Outfile(CONNECT : boolean;
                  TEDGE1, TEDGE2 : ARRN1;
                  TWEIGHT   :  integer;
                  N         :  integer);

var counter : integer;

begin
  rewrite(KruskalOutfile);
  writeln(KruskalOutfile,'  CONNECT is  ',CONNECT);
  if CONNECT = true then
  begin
  writeln(KruskalOutfile,'  Minimum spanning tree edges are    ');
  for counter := 1 to  N-1 do
    begin
      write(KruskalOutfile,'edge ');
      write(KruskalOutfile,TEDGE1[counter]);
      writeln(KruskalOutfile,TEDGE2[counter]);
    end;
    writeln(KruskalOutfile,'Total Weight =  ',TWEIGHT);
  end;
end;

begin (* main *)
  Infile(N,M,ENDV1,ENDV2,WEIGHT,Nextint);
  KRUSKAL(N,M,ENDV1,ENDV2,WEIGHT,CONNECT,TEDGE1,TEDGE2,TWEIGHT);
  Outfile(CONNECT,TEDGE1,TEDGE2,TWEIGHT,N);
end.