//Dijkstra cu heapuri
program distante;
const inf=999999;
type
lista=^date;
date=record
m,cost:longint;
next:lista;
end;
tabel=array[0..50001] of lista;
tabb=array[0..50001] of longint;
buf=array[0..200000] of char;
var
ff1,ff2:buf;
t:tabel; heap,d,sol,pos:tabb;
ok:boolean; a:lista;
nr,n,m,s,i,j,nrn,x,y,z:longint;
f1,f2:text;
procedure swap(var a,b:longint);
var aux:longint;
begin aux:=a; a:=b; b:=aux;
aux:=pos[a]; pos[a]:=pos[b]; pos[b]:=aux;
end;
procedure heapdown(v:longint);
var w:longint;
begin
w:=v*2;
while w<=nrn do begin
if (w<nrn) and (sol[heap[w]]>sol[heap[w+1]]) then w:=w+1;
if sol[heap[v]]>sol[heap[w]] then swap(heap[v],heap[w]) else break;
v:=w; w:=w*2;
end;
end;
procedure heapup(v:longint);
var k:longint;
begin
k:=heap[v];
while (v>1) and (sol[heap[v]]<sol[heap[v div 2]]) do begin
swap(heap[v],heap[v div 2]);
v:=v div 2;
end;
heap[v]:=k;
end;
procedure delet_heap;
begin
swap(heap[1],heap[nrn]); nrn:=nrn-1;
heapdown(1);
end;
begin
assign (f1,'distante.in');
assign (f2,'distante.out');
reset (f1);
rewrite (f2);
settextbuf(f1,ff1);
settextbuf(f2,ff2);
readln (f1,nr);
for i:=1 to nr do begin
readln (f1,n,m,s);
for j:=1 to n do begin read (f1,d[j]); t[j]:=nil; heap[j]:=j; pos[j]:=j; sol[j]:=inf; end;
for j:=1 to m do begin
readln (f1,x,y,z);
new(a); a^.m:=x; a^.cost:=z; a^.next:=t[y]; t[y]:=a;
new(a); a^.m:=y; a^.cost:=z; a^.next:=t[x]; t[x]:=a;
end;
ok:=true; nrn:=n; sol[s]:=0; heapup(s);
repeat
a:=t[heap[1]]; x:=heap[1]; delet_heap;
while a<>nil do begin
if sol[x]+a^.cost<sol[a^.m] then begin
sol[a^.m]:=sol[x]+a^.cost; heapup(pos[a^.m]);
end;
a:=a^.next;
end;
until nrn=0;
ok:=true;
for j:=1 to n do
if d[j]<>sol[j] then begin ok:=false; break; end;
if ok then writeln (f2,'DA') else writeln (f2,'NU');
end;
close (f1);
close (f2);
end.