type ref=^nod; nod=record nod,cost:word; adr:ref; end; const inf=50000005; var v:array[1..50000] of ref; 
heap,poz:array[1..50000] of word; d,br:array[1..50000] of longint; u:ref; t,n,m,i,a,b,c,s,j,x,aux,pa:longint; 
st:array[1..250000] of char; f,g:text; function citire:longint; var ret:longint; begin ret:=0; while (st[pa]>='0') and 
(st[pa]<='9') do begin ret:=ret*10+ord(st[pa])-48; inc(pa); end; inc(pa); citire:=ret; end; procedure perc(p:word); begin 
while (p>1) and (d[heap[p]]<d[heap[p shr 1]]) do begin aux:=heap[p]; heap[p]:=heap[p shr 1]; heap[p shr 1]:=aux; 
poz[heap[p]]:=p; poz[heap[p shr 1]]:=p shr 1; p:=p shr 1; end; end; procedure sift(p:word); var min:word; begin while (p<=x 
shr 1) and ((d[heap[p]]>d[heap[p*2]]) or (d[heap[p]]>d[heap[p*2+1]])) do begin if d[heap[p*2]]<d[heap[p*2+1]] then min:=p*2 
else min:=p*2+1; aux:=heap[p]; heap[p]:=heap[min]; heap[min]:=aux; poz[heap[p]]:=p; poz[heap[min]]:=min; p:=min; end; end; 
begin assign(f,'distante.in'); assign(g,'distante.out'); reset(f);rewrite(g); readln(f,st); pa:=1; t:=citire; for i:=1 to t 
do begin readln(f,st); pa:=1; n:=citire; m:=citire; s:=citire; readln(f,st);pa:=1; for j:=1 to n do begin v[j]:=nil; 
poz[j]:=0; br[j]:=citire; d[j]:=inf; end; for j:=1 to m do begin readln(f,st);pa:=1; a:=citire; b:=citire; c:=citire; if 
v[a]=nil then begin new(v[a]); v[a]^.nod:=b; v[a]^.cost:=c; v[a]^.adr:=nil; end else begin new(u); u^.nod:=b; u^.cost:=c; 
u^.adr:=v[a]; v[a]:=u; end; if v[b]=nil then begin new(v[b]); v[b]^.nod:=a; v[b]^.cost:=c; v[b]^.adr:=nil; end else begin 
new(u); u^.nod:=a; u^.cost:=c; u^.adr:=v[b]; v[b]:=u; end; end; x:=1; heap[1]:=s; poz[s]:=1; d[s]:=0; while x>0 do begin 
a:=heap[1]; heap[1]:=heap[x]; poz[heap[1]]:=1; poz[a]:=0; dec(x); sift(1); u:=v[a]; while u<>nil do begin if 
d[u^.nod]>d[a]+u^.cost then begin d[u^.nod]:=d[a]+u^.cost; if poz[u^.nod]=0 then begin inc(x); heap[x]:=u^.nod; 
poz[u^.nod]:=x; perc(x); end else perc(poz[u^.nod]); end; u:=u^.adr; end; end; for j:=1 to n do if d[j]<>br[j] then break; if 
d[j]<>br[j] then writeln(g,'NU') else writeln(g,'DA'); end; close(f);close(g); end.