(*   INPUT	: The associated datafile for Prim algorithm is called
		  "PrimDatafile".

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

	    	  Rest of data is based on WEIGHT MATRIX.

     Algorithm	: The Prim algorithm produces a minimum spanning tree
		  in a given undirected network with N nodes.

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

		  Similarly, INF, infinity, there is no edge between
	          two nodes, is set to INF=999.

     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	: Prim algorithm is preferred if graphs are small (N<100).
	
		  Prim algorithm depends only on the number of the nodes
		  in the network and not on its density.

		  Kruskal algorithm runs faster for large sparse graphs
		  (N >100).                                             *)





program MST(input,output,PrimDatafile,PrimOutfile);


const  maxnode = 50;
       INF     = 999;

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

var    Nextint    : integer;
       N          : integer;
       W          : ARRNN;
       TEDGE1,  TEDGE2  :  ARRN1;
       TWEIGHT    : integer;
       CONNECT    : boolean;
       PrimDatafile : CHARFILE;
       PrimOutfile  : CHARFILE;



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

var row, column : integer;

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






procedure PRIM(
       N,INF        :integer;
   var W            :ARRNN;
   var CONNECT      :boolean;
   var TEDGE1,TEDGE2:ARRN1;
   var TWEIGHT      :integer);

   var U,I,K,MIN,TCOUNT:integer;
       NEAR,DIST       :ARRN;
begin
   NEAR[1]:=0;
   for I:=2 to N do begin
      NEAR[I]:=1;  DIST[I]:=W[1,I]
   end;
   TCOUNT:=0;  TWEIGHT:=0;
   CONNECT:=true;                             (* INITIALIZATION OVER *)
   while (TCOUNT < N-1) and CONNECT  do begin
      MIN:=INF;
      for K:=2 to N do
         if NEAR[K] <> 0 then
            if DIST[K] < MIN then begin
               U:=K;  MIN:=DIST[K]
            end;
      if DIST[U] >= INF then CONNECT:=false
      else begin
         TCOUNT:=TCOUNT+1;  TWEIGHT:=TWEIGHT+DIST[U];
         TEDGE1[TCOUNT]:=NEAR[U];  TEDGE2[TCOUNT]:=U;
         NEAR[U]:=0;
         for K:=2 to N do
            if NEAR[K] <> 0 then
               if W[K,NEAR[K]] > W[K,U] then begin
                  DIST[K]:=W[K,U]; NEAR[K]:=U
               end
      end  (* ELSE: NOT (DIST[U] >= INF) *)
   end  (* WHILE (TCOUNT < N-1) ... *)
end;  (* PRIM *)





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


var counter : integer;


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



begin (* main  *)
  Infile(N,W,Nextint);
  PRIM(N,INF,W,CONNECT,TEDGE1,TEDGE2,TWEIGHT);
  Outfile(N,CONNECT,TEDGE1,TEDGE2,TWEIGHT);
end.