program MinimalniKostra;
{Urceni minimalni kostry souvisleho
 ohodnoceneho neorientovanoho grafu}

const MaxVrch = 100;    {maximalni pocet vrcholu grafu}
      MaxHran = 1000;   {maximalni pocet hran grafu}

type Hrana = record
             V1, V2: integer;   {spojene vrcholy}
             Delka: integer     {ohodnoceni hrany}
             end;

var Graf: array[1..MaxHran] of Hrana;        {ulozeni grafu}
    Komponenta: array[1..MaxVrch] of integer;   {komponenty}
    N: 1..MaxVrch;            {skutecny pocet vrcholu grafu}
    PomHrana: Hrana;
    K1,K2: integer;
    S,I,J,K: integer;

begin

{Nacteni vstupnich dat:}
write('Pocet vrcholu grafu: ');
readln(N);
writeln('Hrany grafu:  ODKUD  KAM  DELKA');
S:=0;
while not eof do
  begin
  S:=S+1;          {pocet vsech hran grafu}
  with Graf[S] do read(V1, V2, Delka)
  end;

{Setrideni hran podle velikosti od nejkratsi k nejdelsi
 - pro jednoduchost zde pouzijeme jednoduchy tridici
 algoritmus trideni primym vyberem:}
for I:=1 to S-1 do
  begin
  K:=I;
  for J:=I+1 to S do
    if Graf[J].Delka<Graf[K].Delka then K:=J;
  if K<>I then
    begin
    PomHrana:=Graf[K];
    Graf[K]:=Graf[I];
    Graf[I]:=PomHrana
    end
  end;

{Vlastni urceni minimalni kostry grafu
 - nalezena kostra se neuklada, primo se tiskne:}
writeln;
writeln('Hrany tvorici minimalni kostru grafu:');
for I:=1 to N do Komponenta[I]:=I;
  {pocatecni jednoprvkove komponenty souvislosti}
I:=0;
K:=0;               {pocet hran zarazenych do kostry}
while K<N-1 do
  begin
  I:=I+1;           {zkoumana hrana}
  K1:=Komponenta[Graf[I].V1];
  K2:=Komponenta[Graf[I].V2];
  if K1<>K2 then    {hranu I zaradime do kostry}
    begin
    K:=K+1;
    writeln(Graf[I].V1:5,Graf[I].V2:5);
    for J:=1 to N do
      if Komponenta[J]=K2 then Komponenta[J]:=K1
    end
  end

end.