{
Nevem: Brazovits Lajos 
Feladatom volt: gm1000.102
A feladatom eredm‚nye:  11741 s£ly£ fesz¡t“fa
A program 13min 16.23sec alatt futott IP166-n
A program list ja PASCAL programnyelvben: 
}
program Szamitaselemelet;       {Brazovits Lajos}
{I. 11741}                      {Fut si id“: 0.13.16.23}
uses newdelay,crt,dos;
const nmax=5100;           {graf eleinek a szama}
      csucsmax=1000;       {graf csucsinak a szama}
      maxert=1000;
type
      eljellemzo=record
         kp:integer;
         vp:integer;
         suly:integer;
      end;
      tomb=array[1..nmax] of integer;
      elek=array[1..nmax] of eljellemzo;
      elfile=file of eljellemzo;
VAR
el:elek;
s:tomb;
n:integer;

procedure beolvas;
var filenev:string;
    i:integer;
    ff:text;
Begin
     {$i-} assign(ff,'gm1000.118'); reset(ff);{$i+}
     for i:=1 to nmax do
         begin
              readln(ff,el[i].kp,el[i].vp,el[i].suly);
         end;
     close(ff);
End;
procedure kiir(const el:elek);
var i:integer;
    sum:longint;
Begin
     sum:=0;
     for i:=1 to nmax do
         begin
              sum:=sum+el[i].suly;
{             Writeln(el[i].vp);}
         end;
     writeln('sum= ',sum);
End;

procedure uressor(var s:tomb;var n:integer);
Begin n:=0; End;

procedure sorba(var s:tomb;var n:integer; var mit:integer);
var i:integer;
Begin
     i:=1;
     while (i<=n) and (s[i]<>mit) do i:=i+1;
     if i>n then begin
                      n:=n+1;
                      s[n]:=mit;
                 end;
End;

function eleme(const s:tomb;const n:integer;const mi:integer):boolean;
var i:integer;
begin
     i:=1;
     while ((i<=n) and (s[i]<>mi)) do i:=i+1;
eleme:=(i<=n);
end;

function minimumelsulya(var kezd,veg:integer):integer;
Var i:integer;
    min:integer;
Begin
min:=1;
for i:=2 to Nmax do
    begin
         if (el[min].suly > el[i].suly) then min:=i;
    end;
kezd:=el[min].kp;
veg:=el[min].vp;
minimumelsulya:=el[min].suly;
End;

Procedure minkovel(const csucs:integer;const s:tomb;const n:integer;var kezd,veg,hossz:integer);
{Adott csucsbol a legkisebb sulyu olyan el, amelynek a vegpontja nincs a halmazban}
Var i:integer;
Begin
     hossz:=maxert;
     for i:=1 to nmax do
         begin
              if (el[i].kp=csucs)       {kezdopontra kereses}
                 then begin
                      if not(eleme(s,n,el[i].vp)) then
                         begin
                           if (hossz>el[i].suly) then begin
                                                           kezd:=csucs;
                                                           veg:=el[i].vp;
                                                           hossz:=el[i].suly;
                                                           end;
                         end;
                      end;
         end;
    for i:=1 to nmax do
        begin
             if (el[i].vp=csucs)        {vegpontra kereses}
                then begin
                     if not(eleme(s,n,el[i].kp)) then
                        begin
                        if (hossz>el[i].suly) then begin
                                                        kezd:=csucs;
                                                        veg:=el[i].kp;
                                                        hossz:=el[i].suly;
                                                        end;
                        end;
                     end;
        end;
End;

Procedure mohofa;
var kezd,veg,hossz:integer;
    osszsuly,n,elszam:integer;
    s:tomb;
    i:integer;
    joel:eljellemzo;
    van:boolean;
Begin
osszsuly:=minimumelsulya(kezd,veg);
uressor(s,n);
sorba(s,n,kezd);
sorba(s,n,veg);
for elszam:=2 to csucsmax-1 do
    begin
         writeln(elszam,'-ik lepes');
         joel.suly:=1000;
         for i:=1 to n do begin
                          minkovel(s[i],s,n,kezd,veg,hossz);
                          if joel.suly>hossz then begin
                                                  joel.suly:=hossz;
                                                  joel.kp:=kezd;
                                                  joel.vp:=veg;
                                                  end;
                          end;
         if joel.suly<>1000 then begin
         sorba(s,n,joel.kp);sorba(s,n,joel.vp);
         osszsuly:=osszsuly+joel.suly;
         writeln(osszsuly);
                           end;
    end;
Write('A vegleges osszsuly:'); writeln(osszsuly);
End;

BEGIN
clrscr;
beolvas;
mohofa;
{kiir(el);}
repeat until keypressed;
END.