program dijkstra;

{*
 *  Dijkstruv algoritmus, dynamicky. Pocet vrcholu je omezen max. velikosti pameti a delkou longintu
 *  (nejvetsi cele cislo reprezentovatelne v Pascalu). Na zacatku program nacita hrany do BVS
 *  (ne nutne vyvazeneho), z neho potom vytvori haldu, ve ktere spusti algoritmus. Vysledky uklada
 *  zase do BVS, jehoz projitim je vypise.
 *
 *  Tuetschek 2005
 *}
 


type P_Vrchol = ^T_Vrchol;

     P_Hrana  = ^T_Hrana;

     T_Hrana  = record       { pointry na sousedy, spojak }
         v       : P_Vrchol; { pointr na cilovy vrchol }
         d       : longint;  { delka hrany }
         n       : P_Hrana;  { pointr na dalsi hranu v seznamu }
         end;

     T_Vrchol = record
         id      : longint;  { cislo vrcholu }
         h_id    : longint;  { poradi, kde je vrchol pripojeny v halde }
         sousedi : P_Hrana;  { spojak pointru na sousedy }
         d       : longint;  { vzdalenost od zdroje }
         l,p     : P_Vrchol; { pro bin. stromy - naslednici }
         end;


var pocet_vrcholu    : longint; { celkovy pocet vsech vrcholu }
    start            : longint; { cislo pocatecniho vrcholu }
    akt_v_halde      : longint; { akt. pocet vrcholu na halde - dulezite
                                  pro vytvareni haldy }
    posl_vypsany     : longint; { pro vypis - dovypsani poslednich }
    Halda            : P_Vrchol;{ pro uchovani behem behu alg. }
    BVS              : P_Vrchol;{ pro predzpracovani dat,
                                  odkladani vysledku }

const lw_L           = -1; { pro Get_Min, spravne navazani pointru, }
      lw_P           = 1;  { uchovani posledni cesty }
      lw_N           = 0;  { L,P - naposledy se slo vlevo, vpravo }
                           { lw_N - spec. prip - poc. hodnota }


(*  jen pro ladeni
Procedure Vypis_Strom( R : P_Vrchol );
begin;
if ( R = nil ) then
  Exit;

Vypis_Strom ( R^.l );
Writeln( R^.id : 2,' ', R^.h_id : 2,' ', R^.d : 2 );
Vypis_Strom ( R^.p );

end;
*)

{*
 *
 *  INICIALIZACE
 *
 *
 *}

Procedure Vynuluj( R : P_Vrchol );
{ nastavi hodnoty vrcholu na "pocatecni" }
begin;
R^.sousedi := nil;
R^.d := -1;
R^.l := nil;
R^.p := nil;
R^.h_id := 0;
end;


Procedure Init;
{ inicializace promennych,
  musi se na zac. zavolat, jinak program
  nebude fungovat }
begin;
BVS := nil;

{ dulezite - ost. procedury s tim pocitaji !!!: }
New( Halda );
Vynuluj( Halda );
Halda^.d := 0;
Halda^.h_id := 1;

posl_vypsany := 0;
pocet_vrcholu := 0;
start := 0;
akt_v_halde := 1;
end;

{*
 *
 *  POCATECNI NACITANI, VYTVARENI BIN. STROMU
 *
 *
 *}


Function  Get_Vrchol( var R : P_Vrchol; id : longint ): P_Vrchol;
{ zjisti adresu na pointer vrcholu,
  pokud neexistuje, vytvori ho      }
var P : P_Vrchol;
begin;

if (R = nil) then
begin;
  New( P );
  Vynuluj( P );
  R:= P;
  P^.id := id;
  Get_Vrchol := R;
  Exit;
end;

if (id < R^.id) then
  Get_Vrchol:= Get_Vrchol( R^.l, id )
else if (id > R^.id) then
  Get_Vrchol:= Get_Vrchol( R^.p, id )
else
  Get_Vrchol:= R;

end;




Procedure Vloz_Hranu( var R : P_Vrchol; z_id, d, c_id : longint );
{ vlozi hranu na spravne misto do BVS,
  z_id, c_id - cisla vrcholu zdroje a cile,
  d - delka hrany }
var P : P_Vrchol;
    H : P_Hrana;
begin;

if (R = nil ) then
begin;               { vytvoreni noveho node-vrcholu }
  New( P );
  Vynuluj( P );
  R:= P;
  P^.id := z_id;
  New( H );
  H^.d := d;
  H^.n := nil;
  if (c_id = start) then
    H^.v := Halda  { startovaci vrchol je uz od pocatku na vrchu haldy }
  else
    H^.v := Get_Vrchol( BVS, c_id );    { vyhledava pointr na cil. }
  P^.sousedi := H;                      { vrchol v globalnim BVS   }
  Exit;                                 { vsech vrcholu }
end;


if (z_id < R^.id) then   { rekurzivni volani na podstrom BVS }
  Vloz_Hranu( R^.l, z_id, d, c_id )
else if (z_id > R^.id) then
  Vloz_Hranu( R^.p, z_id, d, c_id )
else
begin;  { pridavam novou hranu k existujicimu node-vrcholu }
  New( H );
  H^.d := d;
  H^.n := R^.sousedi;
  if (c_id = start) then
    H^.v := Halda
  else
    H^.v := Get_Vrchol( BVS, c_id );
  R^.sousedi := H;
end;

end;



Procedure Pridej_Ke_Zdroji( d, c_id : longint );
{ spec. pridava hrany startovacimu vrcholu,
  jeho ulozeni na halde uz musi existovat   }
var H : P_Hrana;
begin;
New( H );
H^.d := d;
H^.n := Halda^.sousedi;
H^.v := Get_Vrchol( BVS, c_id );
Halda^.sousedi := H;
end;


Procedure Nacti;
{ nacteni vstupu }
var z_id, d, c_id : longint;
    (*f             : text;(**)
begin;
(*{ ze souboru, pro ladeni}
Assign( f, 'dijkstra.txt' );
Reset( f ); (**)

Readln((* f,(**) pocet_vrcholu, start );
Halda^.id := start;
while (true) do
begin;
  { nacitani po radcich }
  Read((* f,(**) z_id );
  { vyskoci z cyklu, pokud zadam z_id = 0 ) }
  if (z_id <= 0 ) then
    Break;
  Readln((* f,(**) c_id, d );
  { "kontrola" vstupu - po naprosto zjevne
    nekorektnim zadani ukonci program na
    range check error }
  if (z_id = c_id) or (d < 0 ) or (z_id <= 0) or (c_id <= 0) then
    RunError( 201 );


  { sp. prip - ulozeni hrany z poc. vrcholu }
  if (z_id = start) then
    Pridej_Ke_Zdroji( d, c_id)
  { jinak - pridani do BVS }
  else
    Vloz_Hranu( BVS, z_id,d,c_id );
end;
Readln(*(f)(**);
end;

{*
 *
 *  VYTVORENI HALDY
 *
 *
 *}


Procedure Pridej_Do_Haldy( R, N : P_Vrchol; misto : longint);
{ prida do haldy na zadane misto v poradi,
  nekontroluje jestli cesta k nemu existuje }
var pos : longint;
begin;

{ nalezeni prvni platne dvojkove cislice v
  cisle pridavane pozice }
pos := 1 shl 30; { max. pocet vrcholu - maxlongint }
while ( misto and pos = 0 ) do
  pos := pos shr 1;


{ pruchod stromem tesne nad pridavanou
  pozici ( podle jejiho cisla ) }
while (pos and 2 = 0) do
begin;
  pos := pos shr 1;
  if (misto and pos = 0) then
    R := R^.l
  else
    R := R^.p;

end;

{ pripojeni na spravne misto }
N^.h_id := misto;
if (misto and 1 = 0) then
  R^.l := N
else
  R^.p := N;

end;

Procedure Vytvor_Haldu( var R : P_Vrchol );
{ vytvori z BVS haldu,
  pocita s tim, ze v koreni haldy
  uz je zdrojovy vrchol, ze na
  zac. je akt_v_halde  = 1 }
begin;

if (R = nil) then Exit;

Vytvor_Haldu(R^.l);
Vytvor_Haldu(R^.p);


Inc( akt_v_halde );
Pridej_Do_Haldy( Halda, R, akt_v_halde );
R := nil;

end;

{*
 *
 *  DIJKSTRUV ALGORITMUS
 *  - UPRAVY HALDY, RELAX, ODEBRANI MINIMA, ZRUSENI STROMU
 *
 *}



Procedure Presun_V_Halde( var R : P_Vrchol; id, pos : longint );
{ presune prvek cislo id na spravne misto v halde R.
  na zac. volani musi byt pos = 000...010...000, kde
  jednicka je na pozici prvni jednicky v dvojkovem
  zapisu cisla id  }
var P : P_Vrchol;
begin;
{ spec. prip - volani na min. prvek - zmenseni
  uz ho nemuze posunout vys }
if ( pos = 1 ) then Exit;

{ sestup do nizsich pater rekurze,
  zastavi se vzdy nad hledanym   }
if ( pos > 3 ) then
begin;
  pos := pos shr 1;
  if ( id and pos = 0 ) then
    Presun_V_Halde( R^.l, id, pos )
  else
    Presun_V_Halde( R^.p, id, pos );
end;

{ vraceni se - upravovani haldy. - zmensuji d u jednoho
  prvku --> muze nastat jen jeden pripad }

if (((R^.l^.d >= 0) and (R^.l^.d < R^.d)) or
    ((R^.d = -1) and (R^.l^.d >= 0))) then
begin;
  P := R^.l;
  R^.l:= R^.l^.l;
  P^.l:= R;
  R:= P;
  P:= R^.p;
  R^.p := R^.l^.p;
  R^.l^.p := P;
  { prohozeni h_id ( jsou ruzna, takze xor-trik musi fungovat) }
  R^.h_id := R^.h_id xor R^.l^.h_id;
  R^.l^.h_id := R^.h_id xor R^.l^.h_id;
  R^.h_id := R^.h_id xor R^.l^.h_id;
end
else if ((R^.p <> nil) and (((R^.p^.d < R^.d) and ( R^.p^.d >= 0))
        or ((R^.d = -1) and (R^.p^.d >= 0)))) then
begin;
  P := R^.p;
  R^.p:= R^.p^.p;
  P^.p:= R;
  R:= P;
  P:= R^.l;
  R^.l := R^.p^.l;
  R^.p^.l := P;
  { prohozeni h_id }
  R^.h_id := R^.h_id xor R^.p^.h_id;
  R^.p^.h_id := R^.h_id xor R^.p^.h_id;
  R^.h_id := R^.h_id xor R^.p^.h_id;
end;

end;




Procedure Relax( z_d : longint; var H : P_Hrana );
{ snizi vzdalenost podle delky hrany H a z_d - poc. vzdalenosti,
  posune H o 1 dal  }
var pos : longint;
begin;
if ((z_d >= 0) and ((H^.V^.d > z_d + H^.d) or (H^.V^.d = -1))) then
begin;
  { snizi vzdalenost vrcholu }
  H^.V^.d := z_d + H^.d;
  { presune vrchol na spravne misto v halde }
  pos := 1 shl 30;
  while ( pos and H^.V^.h_id = 0) do
    pos := pos shr 1;
  Presun_V_Halde( Halda, H^.V^.h_id, pos );
end;
{ posune index H na dalsi ve spojaku }
H:= H^.n;
end;


Function Get_Min : P_Vrchol;
{ vraci pointer na min. prvek z haldy,
  ten taky z haldy odebere }
var pos       : longint;
    P,Q,R     : P_Vrchol;
    last_way  : shortint;
begin;
{ vraceni minima z haldy, hodnotu pointru halda
  budu dale menit }
Get_Min := Halda;

{ spec. prip - zruseni posl. prvku a cele haldy }
if ( akt_v_halde = 1) then
begin;
  Halda := nil;
  akt_v_halde := 0;
  Exit;
end;

{ vyhledani spravneho prvku - zastavi se o patro nad nim }
P := Halda;
pos := 1 shl 30;
while ( akt_v_halde and pos = 0 ) do
  pos := pos shr 1;
while ( pos and 2 = 0 ) do
begin;
  pos := pos shr 1;
  if ( akt_v_halde and pos = 0 ) then
    P := P^.l
  else
    P := P^.p;
end;

{ presunuti posledniho prvku v halde na zacatek }
if ( P^.p = nil ) then { posledni v halde je levy }
begin;
  if ( akt_v_halde > 3) then
    P^.l^.l := Halda^.l; { spec. prip viz nize }
  P^.l^.p := Halda^.p;   { oba tyto ukazatele puv. ukazuji na nil }
  Q := Halda;
  Halda := P^.l;
  Q^.p := nil;
  Q^.l := nil;
  P^.l := nil;
end else { posledni v halde je pravy }
begin;
  P^.p^.l := Halda^.l;
  if ( akt_v_halde > 3 ) then
    P^.p^.p := Halda^.p;
     { resi spec. prip, pokud jsou na halde jen 3 prvky,
       ukazoval by sam na sebe ( takhle bude ukazovat na nil ) }
  Q := Halda;
  Halda := P^.p;
  Q^.p := nil;
  Q^.l := nil;
  P^.p := nil;
end;
Halda^.h_id := 1; { nastaveni spravneho h_id prvku }
Dec( akt_v_halde );

{ srovnani haldy }
P := Halda;
last_way := lw_N;
while  ( ((P^.l <> nil) and (((P^.l^.d >= 0)and ( P^.l^.d < P^.d)) or
          ((P^.d = -1) and (P^.l^.d >= 0)) ) )  or
         ((P^.p <> nil) and (((P^.p^.d >= 0)and ( P^.p^.d < P^.d)) or
          ((P^.d = -1) and (P^.p^.d >= 0)) ) )) do
begin;
  if ((P^.p <> nil) and (((P^.p^.d >= 0) and (P^.p^.d < P^.l^.d))
     or ((P^.l^.d = -1) and (P^.p^.d >= 0)))) then
  begin; { prohodim s pravym synem }
    Q := P^.p;
    P^.p:= P^.p^.p;
    Q^.p:= P;
    P:= Q;
    Q:= P^.l;
    P^.l := P^.p^.l;
    P^.p^.l := Q;
    P^.h_id := P^.h_id xor P^.p^.h_id;
    P^.p^.h_id := P^.h_id xor P^.p^.h_id;
    P^.h_id := P^.h_id xor P^.p^.h_id;
    case last_way of
    lw_N : begin;
           Halda := P;
           R := P;
           end;
    lw_L : R^.l := P;
    lw_P : R^.p := P;
    end; {case}
    last_way := lw_P;
    R := P;
    P := P^.p;
  end else { s levym }
  begin;
    Q := P^.l;
    P^.l:= P^.l^.l;
    Q^.l:= P;
    P:= Q;
    Q:= P^.p;
    P^.p := P^.l^.p;
    P^.l^.p := Q;
    P^.h_id := P^.h_id xor P^.l^.h_id;
    P^.l^.h_id := P^.h_id xor P^.l^.h_id;
    P^.h_id := P^.h_id xor P^.l^.h_id;
    case last_way of
    lw_N : begin;
           Halda := P;
           R := P;
           end;
    lw_L : R^.l := P;
    lw_P : R^.p := P;
    end; {case}
    last_way := lw_l;
    R := P;
    P := P^.l;
  end;
end;

end;


Procedure Vloz_BVS( var R : P_Vrchol; N : P_Vrchol );
{ vlozi vrchol (vysledek Dijkstra) na spravne misto do BVS }
var P : P_Vrchol;
begin;

if (R = nil ) then
begin;               { pridani na spravne misto }
  R:= N;
  Exit;
end;

if (N^.id < R^.id) then   { rekurzivni volani na podstrom BVS }
  Vloz_BVS( R^.l, N )
else
  Vloz_BVS( R^.p, N );

end;

Procedure Zrus_Strom( R : P_Vrchol );
{ disposne cely BVS/Haldu }
begin;
if ( R = nil) then
  Exit;

Zrus_Strom( R^.l );
Zrus_Strom( R^.p );

Dispose( R );
R := nil;
end;


Procedure Dijkstra_Alg;
{ samotny algoritmus - volani fci Relax, Get_Min,
  ze struktury "Halda" odklada vysledek do stromu "BVS"  }
var P : P_Vrchol;
    H : P_Hrana;
begin;

while ( akt_v_halde > 0 ) do
begin;
  P := Get_Min;    { odebrani minima z haldy }

  if (P^.d = -1) then { v halde uz neni zadny dostupny vrchol,
                        minimum = nekonecno; muzu tedy algoritmus ukoncit }
  begin;
    Zrus_Strom( Halda );
    Exit;
  end;
  (*Writeln('*******', akt_v_halde : 2 );
  Vypis_Strom( Halda );
  Writeln;
  Readln;            (*pro ladeni*)
  H := P^.sousedi;
  while ( H <> nil ) do
  begin;
    Relax( P^.d, H ); { fce relax sama posouva pointer H }
    (*Vypis_Strom( Halda );
    Writeln;
    Readln; (*pro ladeni*)
  end;
  Vloz_BVS( BVS, P ); { ulozeni "vyrizeneho" vrcholu do BVS }
end;

end;


{*
 *
 *  VYPIS VYSLEDKU
 *
 *
 *}



Procedure Vypis_Vysledek( R : P_Vrchol; var last_id : longint);
{ Projde BVS, vypise vysledky, u vrcholu ze/do kterych
  nevede zadna hrana (& nejsou v BVS) si vymysli -1   }
begin;

if ( R = nil) then
  Exit;

Vypis_Vysledek( R^.l, last_id );
Inc( last_id );
while ( last_id < R^.id ) do
begin;
  Writeln( last_id, ' ', '-1' );
  Inc( last_id );
end;
Writeln( R^.id, ' ', R^.d );
Vypis_Vysledek( R^.p, last_id );

end;


{*
 *
 *  HLAVNI PROGRAM
 *
 *
 *}



begin;
Init;                  { provede inicializaci promennych }
Nacti;                 { nacte data }
Vytvor_Haldu( BVS );   { vytvori z dat v BVS haldu }
(*
Writeln( '--------------------------');
Vypis_Strom( Halda );
Writeln;
(*pro ladeni*)
Dijkstra_Alg;          { provede Dijktstra na haldu, vysledky uklada do BVS}
Vypis_Vysledek( BVS, posl_vypsany );
{ posl_vypsany - znaci posl. vrchol zadany na zacatku
  do BVS - posl. ( nejvyssi id ), do ktereho nebo z
  ktereho vubec vede nejaka hrana }
while ( posl_vypsany < pocet_vrcholu ) do
begin;
  Inc( posl_vypsany );
  Writeln( posl_vypsany, ' ', '-1' );
end;
Zrus_Strom( BVS );     { smaze BVS }
end.