{
TASK: NYKSTUKAIV
LANG: PASCAL
}
program snamas;

const
  CKamb = 50;        {daugiausia kambarių aukšte}
  CAuks = 50;        {daugiausia aukštų name}
  CSmurf = 50*50;
  CMaxKamb = CKamb * CAuks; {daugiausia kambarių name}

type
  TJungtys = array[0..CMaxKamb - 1, 0..CMaxKamb - 1] of byte;
  TKamb = longint; {atstumas nuo išėjimo}

  TKambariai = array [0..CMaxKamb - 1] of TKamb;

//  TSmurfai = array [1..CSmurf] of TSmurfas;

  THeap =
    record
      ilgis : longint;
      info : array [1..CMaxKamb] of longint;
    end;

{pora globalių kintamųjų, kad mažiau reikėtų perdavinėti funkcijoms}
var
  kambariai : TKambariai;
  Q : THeap;
  eileje : array [0..CMaxKamb - 1] of boolean;
  eilesnr : array [0..CMaxKamb - 1] of longint;

function parse_kambarys(au, k : longint): longint;
begin
  parse_kambarys := (au - 1)*CAuks + k-1;
end;{parse_kambarys}


function maziausias : longint;
{
išima iš heap'o Q mažiausią elementą ir gražina jį kaip funkcijos rezultatą
}

  procedure heapify(i : longint);
  {
  heapify yra veiksmas kuriuo atstatoma sunaikinta heap'o struktūra
  }
  var
    l, r, smallest, tmp : longint;
  begin
    l := i * 2;
    r := i * 2 + 1;
    if (l <= Q.ilgis) and (kambariai[Q.info[l]] < kambariai[Q.info[i]])
         then smallest := l
         else smallest := i;
    if (r <= Q.ilgis) and (kambariai[Q.info[r]] < kambariai[Q.info[smallest]])
         then smallest := r;
    if smallest <> i then
    begin
      tmp := Q.info[i];
      Q.info[i] := Q.info[smallest];
      Q.info[smallest] := tmp;
      eilesnr[Q.info[i]] := i;
      eilesnr[Q.info[smallest]] := smallest;
      heapify(smallest);
    end;
  end;

var
  rez : longint;

begin
  rez := Q.info[1];
  eileje[rez] := false;
  Q.info[1] := Q.info[Q.ilgis];
  eilesnr[Q.info[1]] := 1;
  Q.ilgis := Q.ilgis - 1;
  heapify(1);
  maziausias := rez;
end;

procedure atnaujink(i : longint);
{
pakitus i-tojo elemento atstumui reikia pertvarkyti eilę taip,
kad ji tenkintų heap'ui keliamus reikalavimus
}
var
  tmp : longint;
begin
  while (i <> 1) and (kambariai[q.info[i]] < kambariai[q.info[i div 2]]) do
  begin
    tmp := q.info[i];
    q.info[i] := q.info[i div 2];
    q.info[i div 2] := tmp;
    eilesnr[q.info[i]] := i;
    eilesnr[q.info[i div 2]] := i div 2;
    i := i div 2;   
  end;
end;

procedure itrauk(i: longint);
begin
  eileje[i] := true;
  Q.ilgis := q.ilgis + 1;
  Q.info[Q.ilgis] := i;
  eilesnr[Q.info[Q.ilgis]] := Q.ilgis;
  atnaujink(Q.ilgis);
end;

var
  jungtys : TJungtys;
  aukstai : array [0..CAuks - 1] of longint;
  smurfai : array [1..CSmurf] of longint;

  f : text;
  nSmurf : longint;
  t1, t2, t : longint;
  nAuks : longint;
  isejimas : longint;

  i, j : longint; {ciklų valdymui}
  nkam1, nkam2, dabkam, nJung : longint;
  au1, au2, laik, atst, pabegs : longint;
  l1, l2 : longint;
begin {snamas}
  for i := 0 to CMaxKamb - 1 do
    for j := 0 to CMaxKamb - 1 do
      jungtys[i, j] := 0;

  assign(f, 'NAMAS.DAT');
  reset(f);
  readln(f, nAuks, nSmurf, nJung);
  {nusiskaitom po kiek yra kambarių aukštuose}
  for i := 0 to nAuks - 1 do
    read(f, aukstai[i]);
  readln(f);
  readln(f, au1, l1);
  {susirandam išėjimą}

  isejimas := parse_kambarys(au1, l1);

  readln(f, t, t1, t2);
  {skaitom smurfus}
  for i := 1 to nSmurf do
  begin
    readln(f, au1, l1);
    smurfai[i] := parse_kambarys(au1, l1); {kuriam kambary smurfas}
  end;
  for i := 1 to nJung do
  begin
    readln(f, au1, l1, au2, l2);
    nkam1 := parse_kambarys(au1, l1);
    nkam2 := parse_kambarys(au2, l2);
    if au1 = au2
      then laik := t1
      else laik := t2;
    jungtys[nkam1, nkam2] := laik;
    jungtys[nkam2, nkam1] := laik;
  end;
  close(f);

  for i := 0 to CMaxKamb - 1 do kambariai[i] := high(longint);
  kambariai[isejimas] := 1;
  {eiles inicializacija}
  for i := 0 to CMaxKamb - 1 do eileje[i] := false;
  Q.ilgis := 0;

  itrauk(isejimas);
  kambariai[isejimas] := t1;
  while Q.ilgis <> 0 do
  begin
    dabkam := maziausias;
    for i := 0 to CMaxKamb - 1 do
      if jungtys[i, dabkam] <> 0 then
    begin
      atst := kambariai[dabkam] + jungtys[i, dabkam];
        if (kambariai[i] > atst) and
           (atst <= t) then
      begin
        kambariai[i] := atst;
        if eileje[i]
          then atnaujink(eilesnr[i])
          else itrauk(i);
      end;
    end;
  end;

  assign(f, 'NAMAS.REZ');
  rewrite(f);
  pabegs := 0;
  for i := 1 to nSmurf do
    if kambariai[smurfai[i]] <= t then inc(pabegs);
  writeln(f, pabegs);
  for i := 1 to nSmurf do
    if kambariai[smurfai[i]] <= t then writeln(f, i);

  close(f);

end. {snamas}