type pnod=^nod;
     nod=record
      c:integer;
      n:word;
      a:pnod;
     end;
var t,sw1,sw2:byte;
    i,x,y,s,n:word;
    v:array[1..50000] of pnod;
    q:array[0..1,0..50000] of word;
    r,rasp:array[1..50000] of longint;
    viz:array[1..50000] of boolean;
    f,g:text;
    p,p1:pnod;
    j,m:longint;
    ok:boolean;
    z:integer;
begin
 assign(f,'distante.in');reset(f);
 assign(g,'distante.out');rewrite(g);
 readln(f,t);
 for j:=1 to t do
  begin
   readln(f,n,m,s);
   for i:=1 to n do
    read(f,rasp[i]);
   for i:=1 to m do
    begin
     readln(f,x,y,z);
     new(p); p^.c:=z; p^.n:=y; p^.a:=v[x]; v[x]:=p;
     new(p); p^.c:=z; p^.n:=x; p^.a:=v[y]; v[y]:=p;
    end;
   for i:=1 to n do
    r[i]:=maxlongint;
   r[s]:=0;
   sw1:=0; sw2:=1; q[0,0]:=1; q[0,1]:=s;
   while q[sw1,0]>0 do
    begin
     q[sw2,0]:=0;
     for i:=1 to n do
      viz[i]:=false;
     for i:=1 to q[sw1,0] do
      begin
       x:=q[sw1,i];
       p:=v[x];
       while p<>nil do
        begin
         if r[x]+p^.c<r[p^.n] then begin
                                    r[p^.n]:=r[x]+p^.c;
                                    if viz[p^.n]=false then begin
                                                             viz[p^.n]:=true;
                                                             inc(q[sw2,0]);
                                                             q[sw2,q[sw2,0]]:=p^.n;
                                                            end;
                                   end;
         p:=p^.a;
        end;
      end;
     sw1:=sw1 xor 1;
     sw2:=sw2 xor 1;
    end;
   ok:=true;
   for i:=1 to n do
    begin
     if r[i]=maxlongint then r[i]:=0;
     if r[i]<>rasp[i] then ok:=false;
    end;
   if ok=true then writeln(g,'DA')
              else writeln(g,'NU');
   for i:=1 to n do begin
                      p:=v[i];
                      while p<>nil do
                       begin
                       p1:=p;
                       p:=p^.a;
                       dispose(p);
                       end;
                      v[i]:=nil;
                    end;

   end;
 close(f);
 close(g);
end.