program graf;
uses crt;
var a,t:array[1..10,1..10]of integer;
    b,c:array[1..10]of integer;
    m1,m,o1,o2,n,i,j,ss,si:integer;
procedure citire;
 begin
   window(10,10,60,15);
   textbackground(5);textcolor(cyan);clrscr;
   write('Introduceti numarul de orase(maxim 10) :');
   readln(n);
   for i:=1 to n-1 do
     for j:=n downto i+1 do
       begin
         readln(a[i,j]);
         a[j,i]:=a[i,j];
       end;
   for i:=1 to n do a[i,i]:=0;
 end;
procedure cautare(k:integer);
 var x,y:integer;
 begin
   for x:=1 to n do
     begin
       if t[k,x]>0 then
         begin t[k,x]:=0;t[x,k]:=0;
           si:=si+a[k,x];
           m:=m+1;c[m]:=x;
           if x=o2 then if ss>si then begin
                                        ss:=si;m1:=m;
                                        for y:=1 to m1 do b[y]:=c[y];
                                      end;
           if x<>o2 then cautare(x);
           si:=si-a[k,x];
           t[k,x]:=a[k,x];
           t[x,k]:=a[x,k];
           c[m]:=0;m:=m-1;
         end;
     end;
 end;
procedure afisare;
 begin
   window(1,1,80,24);textbackground(7);textcolor(13);clrscr;
   if m1=0 then write('Nu exista nici un fel de legatura')
           else
           begin
             write(o1);
             for i:=1 to m1 do write(' ',b[i],' ');
             write('Distanta minima dintre primul si ultimul oras este de '
             ,ss,' km prin orasele afisate mai sus');
           end;
   readln;
 end;
begin
  clrscr;
  citire;
  for i:=1 to n do for j:=1 to n do t[i,j]:=a[i,j];
  window(10,17,60,22);
  textbackground(3);textcolor(magenta);clrscr;
  write('Introduceti numarul primului oras :');
  readln(o1);
  write('Introduceti numarul celui de-al doilea oras :');
  readln(o2);
  si:=0;ss:=maxint;m:=0;m1:=0;
  if a[o1,o2]<>0 then writeln('Exista legatura directa de :',a[o1,o2],' km')
                 else cautare(o1);
  afisare;
end.