{+--------------------------------------------------------------------------+}
{|        The Textbook in Data Structure, Algorithms and Programming        |}
{|              http://w...content-available-to-author-only...c.jp/~hoangle/DSAPTextbook/               |}
{|                                                                          |}
{|    Program: Finding_the_Minimum_Spanning_Tree_using_Kruskal_Algorithm    |}
{|                         Written by Le Minh Hoang                         |}
{|                      Email: dsaptextbook@gmail.com                       |}
{+--------------------------------------------------------------------------+}

{$MODE DELPHI} (*This program uses 32-bit Integer [-2^31 .. 2^31 - 1]*)
program Finding_the_Minimum_Spanning_Tree_using_Kruskal_Algorithm;
(*
IMPORTANT NOTES FOR COMPATIBILITY:
==================================
- This program is especially written for running under Windows 32 bit and
  Free Pascal IDE. Therefore, 32-bit Integer type is used to result in the
  best performance with the {$MODE DELPHI} compiler directive of FPK for
  Windows.
- If you use Borland Turbo Pascal 7 for DOS, you may have to reduce the
  data structure to deal with the limited memory. In addition, BP7 does not
  support 32-bit Integer type, it causes some Integer variables would have
  to be converted into LongInt variables.
- If you prefer to compile under Delphi, you can simply convert the source
  code as follows:
  + Replace the type "Text" with the type "TextFile"
  + Change all procedure calls "Assign(., .)" to "AssignFile(., .)" and
    "Close(.)" to "CloseFile(.)"
  + Remove the {$MODE DELPHI} and add the {$APPTYPE CONSOLE} compiler 
    directive to the beginning of this program
-----------------------------------------------------------------
Please report any errors to: dsaptextbook@gmail.com, MANY THANKS!
-----------------------------------------------------------------
*)
const
  InputFile  = '';
  OutputFile = '';
  maxV = 1000;
  maxE = (maxV - 1) * maxV div 2;
type
  TEdge = record    			
    u, v, c: Integer;		
    Mark: Boolean;			
  end;
var
  e: array[1..maxE] of TEdge; 			
  Lab: array[1..maxV] of Integer;		
  n, m: Integer;
  Connected: Boolean;

procedure LoadGraph;		
var
  i: Integer;
  f: Text;
begin
  Assign(f, InputFile); Reset(f);
  ReadLn(f, n, m);
  for i := 1 to m do
    with e[i] do
      ReadLn(f, u, v, c);
  Close(f);
end;

procedure Init;
var
  i: Integer;
begin
  for i := 1 to n do Lab[i] := -1;			
  for i := 1 to m do e[i].Mark := False;
end;

function GetRoot(v: Integer): Integer;	
begin
  while Lab[v] > 0 do v := Lab[v];
  GetRoot := v;
end;

procedure Union(r1, r2: Integer);				
var
  x: Integer;
begin
  x := Lab[r1] + Lab[r2];
  if Lab[r1] > Lab[r2] then
    begin
      Lab[r1] := r2;
      Lab[r2] := x;
    end
  else
    begin
      Lab[r1] := x;
      Lab[r2] := r1;
    end;
end;

procedure AdjustHeap(root, last: Integer);		
var
  Key: TEdge;
  child: Integer;
begin
  Key := e[root];
  while root * 2 <= Last do
    begin
      child := root * 2;
      if (child < Last) and (e[child + 1].c < e[child].c)
        then Inc(child);
      if Key.c <= e[child].c then Break;
      e[root] := e[child];
      root := child;
    end;
  e[root] := Key;
end;

procedure Kruskal;
var
  i, r1, r2, Count, a: Integer;
  tmp: TEdge;
begin
  Count := 0;
  Connected := False;
  for i := m div 2 downto 1 do AdjustHeap(i, m);
  for i := m - 1 downto 0 do
    begin
      tmp := e[1]; e[1] := e[i + 1]; e[i + 1] := tmp;
      AdjustHeap(1, i);
      r1 := GetRoot(e[i + 1].u); r2 := GetRoot(e[i + 1].v);
      if r1 <> r2 then						
        begin
          e[i + 1].Mark := True;
          Inc(Count);							
          if Count = n - 1 then		
            begin
              Connected := True;
              Exit;
            end;
          Union(r1, r2);					
        end;
    end;
end;

procedure PrintResult;
var
  i, Count, W: Integer;
  f: Text;
begin
  Assign(f, OutputFile); Rewrite(f);
  if not Connected then
    WriteLn(f, 'Error: Graph is not connected')
  else
    begin
      WriteLn(f, 'Minimum spanning tree: ');
      Count := 0;
      W := 0;
      for i := 1 to m do								
        with e[i] do
          begin
            if Mark then								
              begin
                WriteLn(f, '(', u, ', ', v, ') = ', c);
                Inc(Count);
                W := W + c;
              end;
            if Count = n - 1 then Break;		
          end;
      WriteLn(f, 'Weight = ', W);
    end;
  Close(f);
end;

begin
  LoadGraph;
  Init;
  Kruskal;
  PrintResult;
end.