program MinCesta3;
{Nalezeni nejlepsi cesty v ohodnocenem grafu}
{Dijkstruv algoritmus s vice kriterii}

const MaxVrch = 100;       {max. pripustny pocet vrcholu}

var Cena, Cas: array[1..MaxVrch,1..MaxVrch] of integer;
          {ohodnoceni hran grafu ve tvaru matic vzdalenosti}
    HC, HT: array[1..MaxVrch] of integer;  {hodnoty vrcholu}
    Docas: array[1..MaxVrch] of boolean;   {docasna hodnota}
    P: array[1..MaxVrch] of 1..MaxVrch; {predchudci vrcholu}
    N: 1..MaxVrch;               {pocet vsech vrcholu grafu}
    Start, Cil: 1..MaxVrch;      {vychozi a cilove mesto}
    Pruchod: boolean;            {pokracovat v pruchodu}
    NovaCena: integer;           {mozne zlepseni HC vrcholu}
    NovyCas: integer;            {mozne zlepseni HT vrcholu}
    i,j: integer;

begin

{Nacteni vstupnich dat a inicializace:}
write('Pocet mest: ');
readln(N);
write('Cislo vychoziho a ciloveho mesta: ');
readln(Start, Cil);
for i:=1 to N do
  begin
  HC[i]:=maxint;
  HT[i]:=maxint;
  Docas[i]:=true;
  for j:=1 to N do
    begin Cena[i,j]:=maxint; Cas[i,j]:=maxint end;
  end;
writeln('Autobusove linky ve tvaru "odkud, kam, jizdne, cas":');
while not eof do
  begin
  read(i,j);
  read(Cena[i,j],Cas[i,j]);
  Cena[j,i]:=Cena[i,j];
  Cas[j,i]:=Cas[i,j]
  end;
HC[Start]:=0;
HT[Start]:=0;
Pruchod:=true;

{Pruchod grafem:}
while Docas[Cil] and Pruchod do
  begin
  j:=Cil;     {hledame vrchol s minimalni docasnou hodnotou}
  for i:=1 to N do
    if Docas[i] and (HC[i]<HC[j]) then j:=i;
  {vybran vrchol j}
  if HC[j]=maxint then
    Pruchod:=false    {Cil je nedostupny}
  else
    begin
    Docas[j]:=false;  {vrchol j ma trvalou hodnotu}
    for i:=1 to N do
      if Cena[j,i] < maxint then
        begin
        NovaCena := HC[j]+Cena[j,i];
        NovyCas := HT[j]+Cas[j,i];
        if NovaCena < HC[i] then
          begin
          HC[i]:=NovaCena;       {kratsi cesta do vrcholu i}
          HT[i]:=NovyCas;        {cas na nove ceste do i}
          P[i]:=j                {novym predchudcem i je j}
          end
        else
          if NovaCena = HC[i] then
                 {nalezena jina cesta stejne minimalni ceny}
            if NovyCas < HT[i] then  {kratsi cas}
              begin
              HT[i]:=NovyCas;     {cas na nove ceste do i}
              P[i]:=j             {novym predchudcem i je j}
              end
        end
    end
  end;

{Vypsani nejkratsi cesty:}
if Docas[Cil] then
  writeln('Cilove mesto neni autobusovymi linkami dostupne',
          ' ze zadaneho vychoziho mesta!')
else
  begin
  writeln('Cena jizdneho na nejlevnejsi ceste z mesta ',
          Start,' do mesta ', Cil,': ', HC[Cil]);
  writeln('Nejmensi mozna doba jizdy na teto nejlevnejsi ',
          'ceste: ', HT[Cil]);
  writeln('Vybrana nejlepsi cesta v obracenem poradi mest');
  writeln('(od ciloveho mesta k vychozimu):');
  i:=Cil;
  while i<>Start do
    begin write(i:5); i:=P[i] end;
  writeln(Start:5)
  end

end.