program Bellman_Ford;

var a:array[1..100,1..100] of longint;
    v,c:array[1..100] of longint;
    q1,q2,q3,z,q,m,i,j,n,start:integer;
    f,g:text;
    ok:boolean;




begin
assign(g,'distante.out');
rewrite(g);
assign(f,'distante.in'); reset(f);
readln(f,q);
for z:=1 to q do
begin
readln(f,n,m,start);
for i:=1 to n do read(f,v[i]);
readln(f);

for i:=1 to m do begin
    begin
    readln(f,q1,q2,q3);
    a[q1,q2]:=q3;
    end;
    c[i]:=maxint;
end;


for j:=1 to n do

if a[start,j]<>0 then
         c[j]:=a[start,j];

for i:=1 to n do
    for j:=1 to n do
if i<>j then
if (i<>start) and (j<>start) and
   (c[i]+a[i,j]<c[j]) and (a[i,j]<>0) then
                c[j]:=c[i]+a[i,j];

ok:=true;
for i:=1 to n do
if i<>start then
if c[i]<>v[i] then ok:=false;
if ok then
writeln(g,'DA') else
writeln(g,'NU');
end;
close(f);
close(G);
end.