program distante;
const Nmax=50000;
      infinit=50000001;
type pnod=^nod;
     nod=record
               next:pnod;
               link,cost:longint;
         end;
var t,tt:byte;
    s,n,m,i,j,dimheap:longint;
    g:array[1..Nmax]of pnod;
    d,dbun,heap,pheap:array[1..Nmax]of longint;
    f,fout:text;
    marcaj:pointer;
    p:pnod;

procedure citire;
var a,b,c:word;
begin
readln(f,n,m,s);
for i:=1 to n do
    read(f,d[i]);
mark(marcaj);
for i:=1 to n do begin
    new(g[i]);
    g[i]^.next:=nil;
end;
for i:=1 to m do begin
    read(f,a,b,c);
    {a->b}
    new(p);
    p^.link:=b;
    p^.cost:=c;
    p^.next:=g[a]^.next;
    g[a]^.next:=p;
    {b->a}
    new(p);
    p^.link:=a;
    p^.cost:=c;
    p^.next:=g[b]^.next;
    g[b]^.next:=p;
end;
end;

procedure insert_heap(nod:longint);
var t,f:integer;
    aux:longint;
begin
inc(dimheap);
heap[dimheap]:=nod;
pheap[nod]:=dimheap;
f:=dimheap;
t:=dimheap div 2;
while t>0 do begin
      if (dbun[heap[t]]>dbun[heap[f]]) then
         begin
         aux:=heap[f];
         heap[f]:=heap[t];
         heap[t]:=aux;
         pheap[heap[f]]:=f;
         pheap[heap[t]]:=t;
         f:=t;
         t:=f div 2;
         end
      else break;
end;
end;

procedure update_heap(nod:longint);
var t,f:integer;
    aux:longint;
begin
f:=pheap[nod];
t:=f div 2;
while t>0 do begin
      if (dbun[heap[t]]>dbun[heap[f]]) then
         begin
         aux:=heap[f];
         heap[f]:=heap[t];
         heap[t]:=aux;
         pheap[heap[f]]:=f;
         pheap[heap[t]]:=t;
         f:=t;
         t:=f div 2;
         end
      else break;
end;
end;

procedure out_heap(nod:longint);
var t,f:integer;
begin
t:=1;
f:=2;
while t*2<=dimheap do begin
      if (f+1<=dimheap) then
         if (dbun[heap[f]]<dbun[heap[f+1]]) then
            begin
            heap[t]:=heap[f];
            pheap[heap[t]]:=t;
            t:=f;
            f:=t*2;
            end
            else
            begin
            heap[t]:=heap[f+1];
            pheap[heap[t]]:=t;
            t:=f+1;
            f:=t*2;
            end
       else begin
            heap[t]:=heap[f];
            pheap[heap[t]]:=t;
            t:=f;
            f:=t*2;
            end;
end;
   heap[t]:=heap[dimheap];
   pheap[heap[t]]:=t;
   dec(dimheap);
   if (t<=dimheap) then update_heap(heap[t]);
end;

procedure dijkstra(nod:longint);
begin
{initializari}
for i:=1 to n do begin
    dbun[i]:=infinit;
    pheap[i]:=0;
end;
{inserez nodul de pornire}
pheap[nod]:=1;
heap[1]:=nod;
dimheap:=1;
dbun[1]:=0;
{heap dijkstra}
while dimheap>0 do begin
      nod:=heap[1];
      p:=g[nod]^.next;
      while p<>nil do begin
      {caut cost mai bun}
            if (dbun[nod]+p^.cost<dbun[p^.link]) then begin
               dbun[p^.link]:=dbun[nod]+p^.cost;
               {este deja in heap?}
               if (pheap[p^.link]<>0) then update_heap(p^.link)
                  {nu este in heap si il introduc}
                  else insert_heap(p^.link);
             end;
     {avansez in lista cu vecini}
     p:=p^.next;
     end;
     {scot nodul din heap}
     out_heap(nod);
end;
end;

procedure afisare;
begin
for i:=1 to n do
    if (d[i]<>dbun[i]) then begin
                            writeln(fout,'NU');
                            exit;
                            end;
writeln(fout,'DA');
end;

begin
assign(f,'distante.in');reset(f);
assign(fout,'distante.out');rewrite(fout);
readln(f,t);
for tt:=1 to t do begin
    citire;
    dijkstra(s);
    afisare;
    release(marcaj);
end;
close(f);
close(fout);
end.