var N:integer;                                  {počet měst}
    D,E:array[1..N] of array[1..N] of integer;  {D - délky silnic mezi městy,
			                         D[i][i]="nekonečno",
						 místo neexistujících je také "nekonečno",
			                         E - nastaveny na 0}
    P:array[1..N] of integer;                   {posloupnost křižovatek v min kružnici, končí nulou} 
    i,j,k,min_i,min_j,min:integer;
begin
  Nacti_a_inicializuj(E,D,N);
  min:=maxint;                                  {zatím žádná kružnice}
  for k:=3 to N do begin                        {S=(1..k-1)}
    for i:=1 to k-2 do                          {hledám nejmenší kružnice obsahující k}
      for j:=i+1 to k-1 do
	 if (D[i][k]+D[k][j]+D[i][j]<min) then  {i-k a j-k musí být přímo hrany}
	begin 
	  min:=D[i][k]+D[k][j]+D[i][j];
	  min_i:=i;
	  min_j:=j;
	end;
    Pamatuj(P,E,i,j,k);                         {do P si zapamatuj si novou min. kružnici z i do j s k}
    for i:=1 to k-1 do                          {podle upraveného F-W zjisti nové lepší cesty}
      for j:=1 to k-1 do begin
        if D[i][k]+D[k][j]<D[i][j] then begin D[i][j]:=D[i][k]+D[k][j]; E[i][j]:=k; end;
	if D[i][j]+D[j][k]<D[i][k] then begin D[i][k]:=D[i][j]+D[j][k]; E[i][k]:=MAX(E[i][j],j); end;
      end;
  end;
  Vypis(P,min);                                 {pokud min="nekonečno", žádná kružnice neexistuje}
end.