{$B-}
program   shortpath(input,output);
{پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–}
 {پ–                                                            پ–}
 {پ–           گ”  —‌  ‰ب  ٹw  ‰‰  ڈK  ‚h                       پ–}
 {پ–                                                            پ–}
 {پ–    چu    ژt    –¼  پF  –é   ‹v   ’|   •v                   پ–}
 {پ–                                                            پ–}
 {پ–    ٹw  گ¶  ژپ  –¼  پF  ‘‌   ‘ٍ   ‘P   ژq                   پ–}
 {پ–                                                            پ–}
 {پ–    ٹw گ¶ ڈط ”ش چ†  پF  ‚Q ‚P ‚r ‚r ‚P ‚P ‚T ‚X             پ–}
 {پ–                                                            پ–}
 {پ–    ‘ه    ٹw    –¼  پF  “Œ    ٹC    ‘ه    ٹw                پ–}
 {پ–                                                            پ–}
 {پ–    ٹw •” ٹw ‰ب –¼  پF  —‌ ٹw •”   ڈî •ٌ گ” —‌ ٹw ‰ب        پ–}
 {پ–                                                            پ–}
 {پ–    ‰غ    ‘è    –¼  پF  SHORTEST-PATH                       پ–}
 {پ–                                                            پ–}
 {پ–    ژg  —p  Œ¾  Œê  پF  ‚o  ‚پ  ‚“  ‚ƒ  ‚پ  ‚Œ              پ–}
 {پ–                                                            پ–}
 {پ–    چى    گ¬    “ْ  پF  ‚P ‚X ‚W ‚T ”N ‚X Œژ                پ–}
 {پ–                                                            پ–}
 {پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–پ–}


const
          maxnode = 9;
type
          mat = array[1..maxnode, 1..maxnode] of integer;
          plist = array [0..maxnode] of integer;
          nodeptr = ^node;
          node = record
                   vtx  :integer;
                   wgt  :integer;
                   link :nodeptr;
                 end;
var
          x,y,i,j :integer;
          w,v     :integer;
          parent  :plist;
          adjmat,wgtmat  :mat;

{
external procedure short(v,w: integer;var adjmat,wgtmat:mat;
                         var parent:plist);
 }
{$I B:SHORT.SRC}

procedure readadj;
var
  i,j :integer;
  adjfile : text;
begin
  assign(adjfile,'B:ADJ');
  reset(adjfile);
  for i:=1 to maxnode do
    begin
      for j:= 1 to maxnode do read(adjfile,adjmat[i,j]);
      readln(adjfile);
    end;
  close(adjfile)
end;

procedure readwgt;
var
  i,j :integer;
  wgtfile : text;
begin
  assign(wgtfile,'B:WGT');
  reset(wgtfile);
  for i:=1 to maxnode do
    begin
      for j:= 1 to maxnode do read(wgtfile,wgtmat[i,j]);
      readln(wgtfile);
    end;
  close(wgtfile)
end;

begin
  readadj;
  readwgt;
  readln(v,w);
  short(v,w,adjmat,wgtmat,parent);
  x:= w;
   while x <> v do
    begin
      writeln(lst, parent[x] :8,x:8);
      x:=parent[x];
    end;
end.
