type muchie=record
            x,y,cost:longint;
            end;
const q=200000000;{asta trebe neaparat asa :P remember??
        dak nu remember at da prima muchie fara sa plece din sursa
        si fara sa aiba vreun vecin sursa}
var v:array[1..100001]of muchie;
    d,tz:array[1..50001]of longint;
    f,g:text;
    n,poz,pozz:word;
    m,i,s,t,ss:longint;

procedure bellmanford;
var modif:boolean;
begin
repeat
modif:=false;
for i:=1 to m do begin
          s:=d[v[i].x]+v[i].cost;
          poz:=v[i].y;
          if s<d[poz] then begin
                           d[poz]:=s;
                           modif:=true;
                           end;
          s:=d[v[i].y]+v[i].cost;
          poz:=v[i].x;
          if s<d[poz] then begin
                      d[poz]:=s;
                      modif:=true;
                      end;
          end;
until not modif;
end;

function verif:boolean;
var i:longint;
begin
verif:=true;
for i:=1 to n do if d[i]<>tz[i] then begin
         verif:=false;
         break;
         end;end;

begin
assign(f,'distante.in');reset(f);
assign(g,'distante.out');rewrite(g);
read(f,t);

while t>0 do begin
read(f,n,m,s);
for i:=1 to n do begin
         read(f,tz[i]);
         d[i]:=0;
         end;
for i:=1 to m do begin
    read(f,poz,pozz,ss);
    v[i].x:=poz;
    v[i].y:=pozz;
    v[i].cost:=ss;
    if poz=s then d[pozz]:=ss;
    if pozz=s then d[poz]:=ss;
end;
for i:=1 to n do if d[i]=0 then d[i]:=q;
d[s]:=0;
bellmanford;
if verif then writeln(g,'DA')
         else writeln(g,'NU');

dec(t);
end;

close(g);
end.