program distante;
const
pinfinit=maxlongint;
type long=1..50000;
     pnod=^nod;
     nod=record
         nod:long;
         i:0..1000;
         urm:pnod;
         end;
     cheie=record
           val:longint;
           poz:long;
           end;
     vec=array[1..50000]of long;
     vect=array[1..50000]of longint;
var a:array[1..50000]of pnod;
    d:array[1..50000]of record
                        d:longint;
                        s:0..1;
                        end;
    d1:^vect;
    id:^vec;
    h:array[1..50000]of cheie;
    i,poz,n,m,dheap,he,r:longint;
    p:pnod;
    q,t:byte;
    ok:boolean;
    min:longint;
    g,f:text;
procedure citire;
var z,y,x,i:longint;

begin
read(f,n,m,r);
for i:=1 to n do begin a[i]:=nil;read(f,d1^[i]); d[i].d:=pinfinit; d[i].s:=0; end;
for i:=1 to m do begin
 read(f,x,y,z); new(p); p^.nod:=y; p^.i:=z; p^.urm:=a[x]; a[x]:=p; end;
end;
procedure recon_heap(i:longint);
var l,r,max:longint;
    aux:cheie;
begin
l:=i shl 1;
r:=l+1;
if (l<=dheap)and(h[l].val<h[i].val) then max:=l
                        else max:=i;
if (r<=dheap)and(h[r].val<h[max].val) then max:=r;
if max<>i then
          begin

          if ok then begin id^[h[max].poz]:=id^[h[max].poz] div 2;
                       id^[he]:=max;end;
          aux:=h[i]; h[i]:=h[max]; h[max]:=aux;

          recon_heap(max);
          end;
end;
procedure heap;
begin
for i:=n div 2 downto 1 do
  recon_heap(i);
end;
procedure dec_key(i:longint;val:longint);
var aux:cheie;
    a1:longint;
begin
h[i].val:=val;

while (i>1) and (h[i div 2].val>h[i].val) do
begin
aux:=h[i];
 a1:=id^[h[i].poz];
 id^[h[i].poz]:=id^[h[i div 2].poz];
 id^[h[i div 2].poz]:=a1;
 h[i]:=h[i div 2]; h[i div 2]:=aux;
i:=i div 2;
end;
end;
begin {pp}
assign(f,'distante.in'); reset(f);
assign(g,'distante.out'); rewrite(g);
new(d1);
read(f,t);
for q:=1 to t do
begin
citire;
d[r].s:=1;
p:=a[r];
while p<>nil do
 begin
 d[p^.nod].d:=p^.i;
 p:=p^.urm;
 end;
d[r].d:=0;
dheap:=0;
new(id);
for i:=1 to n do
 if i<>1 then begin
              inc(dheap);
              h[dheap].val:=d[i].d;
              h[dheap].poz:=i;
              end;
ok:=false;
heap;
for i:=1 to dheap do id^[h[i].poz]:=i;

while dheap>0 do
begin
ok:=true;
min:=pinfinit;
poz:=0;
poz:=h[1].poz;
min:=h[1].val;
if min=pinfinit then break;
h[1]:=h[dheap]; id^[h[dheap].poz]:=1;
  dec(dheap);
  he:=h[1].poz;
  recon_heap(1);
d[poz].s:=1;
p:=a[poz];
while p<>nil do
   begin
if d[p^.nod].s=0 then if d[p^.nod].d>d[poz].d+p^.i then
             begin
           d[p^.nod].d:=d[poz].d+p^.i;
           dec_key(id^[p^.nod],d[p^.nod].d);
             end;

   p:=p^.urm;
    end;
end;
dispose(id);
ok:=true;
for i:=1 to n do if (d[i].d<>d1^[i])and(d1^[i]<>0) then begin
                             ok:=false; break;end;
if ok then writeln(g,'DA') else writeln(g,'NU');
end;
close(g);                                       close(f);
end.