procedure short(v,w:integer;var adjmat,wgtmat: mat;
                var parent: plist);
const
          maxnode = 9;
label
          999;
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
          ptr :nodeptr;
          e1,e2:integer;
          x,y,i,j :integer;
          v2link  :array [0..maxnode] of integer;
          vset    :array [0..maxnode] of integer;
          adjlist :array [0..maxnode] of nodeptr;
          ecount  :integer;
          a,b,c,e,f,g,h,
          nowptr, newptr:nodeptr;
          D       :ARRAY [1..maxnode] of integer;

function min_d:integer;
  var
    min,i,min_idx:integer;
  begin
    min:=9999;
    min_idx:=maxnode +1;
    for i:=1 to maxnode do
      if vset[i]=2  then
        if d[i] < min then
          begin
            min:=d[i];
            min_idx:=i;
          end;
    min_d:=min_idx;
  end;

procedure remove(x :integer);
   var    link : integer;
  begin
      link:=0;
      while(v2link[link]= x) or (v2link[link]= 0) do
      link:= v2link[link];
      if v2link[link]= x then
      v2link[link]:= v2link[v2link[link]];
  end;

procedure makeadj;
  var
    root,ptr: nodeptr;
    i,j : integer;
  begin
    for i:= 1 to maxnode do
      begin
        root:= nil;
        for j:= 1 to maxnode do
          if adjmat [i,j]=1 then
            begin
              new(ptr);
              with ptr^ do
                begin
                  vtx:= j;
                  wgt:= wgtmat[i,j];
                  link:= root;
                end;
              root:= ptr;
            end;
        adjlist[i]:= root;
      end;
  end;

begin
  makeadj;
  vset[v]:= 1;
  x:=v;
  d[v]:= 0;
  v2link[0]:=0;
  for i := 2 to maxnode do vset[i]:=3;
  while x <> w do
    begin
      ptr := adjlist[x];
      while ptr <> nil do
        begin
          y := ptr^.vtx;
          if (vset[y] = 2) and (d[x]+ptr^.wgt < d[y]) then
            begin
              parent[y] := x;
              d[y] := d[x]+ptr^.wgt;
            end;
          if vset[y] = 3 then
            begin
              vset[y] := 2;
              v2link[y] := v2link[0];
              v2link[0] := y;
              parent[y] := x;
              d[y] := d[x]+ptr^.wgt;
            end;
          ptr:=ptr^.link;
        end;
      if v2link[0] = 0 then
        begin
          writeln(lst,'no path to ',w);
          goto 999
        end;
      y:= min_d;
      remove(y);
      vset[y] := 1;
      x:=y;
    end;
    999: ;
end;