Program Kraskals; {Kraskala algoritms karkasa ar minimaalo svaru atrasanai neorienteetaa grafaa}

uses CRT,DOS;

Const
    nVertex=50; {Virsotnu maksimaalais skaits}
    nRib=1000;  {Maksimaalais skautnu skaits}
    
Type
    TypeVertex=array[1..nVertex] of Integer;
    TypeRib=array[1..nRib] of Integer;
    
Var
    f       :Text;          {Teksta fails}
    nX      :Integer;       {Grafa virsotnu skaits}
    nU      :Integer;       {Grafa skautnu skaits}
    Mark    :TypeVertex;    {Virsotnu iezimes}
    X       :TypeVertex;    {Grafa virsotnu saraksts}
    U       :TypeRib;       {Grafa skautnu saraksts}
    nUo     :Integer;       {Karkasa skautnu skaits}
    Uo      :TypeRib;       {Karkasa skautnes}
    We      :TypeRib;       {Grafa skautnu svari}
    Wt      :LongInt;       {Minimaalaa svara karkasa svars}
    
Procedure Init; 

Var
    i,j,m   :Integer;
begin
    for i:=1 to 2*nU do Uo[i]:=1;
    for i:=1 to 2*nU do
        for j:=i+1 to 2*nU do if Uo[j]=1 then
            if U[j]=U[i] then Uo[j]:=0;
    nX:=0;
    for i:=1 to 2*nU do
        if Uo[i]=1 then begin
            nX:=nX+1;
            X[nX]:=U[i];
        end;
    for i:=1 to 2*nU do
        for m:=1 to nX do
            if U[i]=X[m] then begin U[i]:=m; break; end;
end;

Procedure Sort;

Var
    i,j,k   :Integer;
    w       :Integer;
begin
    for i:=1 to nU do
        for j:=1 to nU-i do
            if We[j]>We[j+1] then begin
                w:=We[j]; We[j]:=We[j+1]; We[j+1]:=w;
                w:=U[2*j-1]; U[2*j-1]:=U[2*(j+1)-1];
                U[2*(j+1)-1]:=w;
                w:=U[2*j]; U[2*j]:=U[2*(j+1)]; U[2*(j+1)]:=w;
            end;
end;

Procedure Ostov;

Var
    i,x,y,z :Integer;
    sU      :Integer;
begin
    for i:=1 to nX do Mark[i]:=i;
    Sort;
    nUo:=0;
    sU:=1;
    while nUo<nX-1 do begin
        x:=U[2*sU];
        y:=U[2*sU-1];
        if Mark[x]<>Mark[y] then begin
            nUo:=nUo+1;
            Uo[nUo]:=sU;
            z:=Mark[y];
            for i:=1 to nX do if Mark[i]=z then
Mark[i]:=Mark[x];
        end;
        sU:=sU+1;
    end;
end;

Var
    i,j :Integer;
begin
    Assign(f,'Kraskals.in');
    Reset(f);
    Read(f,nU);
    for i:=1 to nU do Read(f,U[2*i-1]);
    for i:=1 to nU do Read(f,U[2*i]);
    for i:=1 to nU do Read(f,We[i]);
    Close(f);
    Assign(f,'Kraskals.out');
    Rewrite(f);
    Init;
    Sort;
    WriteLn(f,'nU =',nU:3);
    WriteLn(f,'nX =',nX:3);
    Write(f,'X  ='); for i:=1 to nX do Write(f,X[i]:3);
    WriteLn(f); Write(f,'u1 =');
    for i:=1 to nU do Write(f,X[U[2*i-1]]:3);
    WriteLn(f); Write(f,'u2 =');
    for i:=1 to nU do Write(f,X[U[2*i]]:3);
    WriteLn(f); Write(f,'We =');
    for i:=1 to nU do Write(f,We[i]:3); WriteLn(f);
    Ostov;
    Write(f,'uo1 =');
    for i:=1 to nUo do Write(f,X[U[2*Uo[i]-1]]:3);
    WriteLn(f); Write(f,'uo2 =');
    for i:=1 to nUo do Write(f,X[U[2*Uo[i]]]:3);
    WriteLn(f); Write(f,'Woe =');
    for i:=1 to nUo do Write(f,We[Uo[i]]:3); WriteLn(f);
    Wt:=0;
    for i:=1 to nUo do Wt:=Wt+We[Uo[i]];
    Write(f,'Svars=',Wt:3);
    Close(f);
end.