program pascal;
var a:array[1..5000,1..5000] of 0..1000;
    viz:array[0..50000] of 0..1;
    d,d1:array[0..50000] of longint;
    n,i,j,k,t,q,m,s:longint;
    f,g:text;

procedure citire_graf(var n:longint);
var i,j,k,c:longint;
begin
   read(f,n,m,s);
   for i:=1 to n do
      read(f,d1[i]);
   for i:=1 to m do
      begin
         read(f,j,k,c);
         a[j,k]:=c;
         a[k,j]:=c;
      end;
end;

procedure dijkstra(nod:longint);
var k:longint;
begin
   viz[nod]:=1;
   for k:=1 to n do
      begin
         if a[nod,k]<>0 then
            if (d[k]>d[nod]+a[nod,k]) then
               begin
                  d[k]:=d[nod]+a[nod,k];
                  dijkstra(k);
               end;
      end;
end;

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

begin
   assign(f,'distante.in');
   reset(f);
   assign(g,'distante.out');
   rewrite(g);
   read(f,t);
   for q:=1 to t do
   begin
      citire_graf(n);
      for i:=1 to n do
         begin
            viz[i]:=0;
            d[i]:=5000;
         end;
      d[1]:=0;
      dijkstra(s);
      if identic then
         writeln(g,'DA')
      else
         writeln(g,'NU');
   end;
   close(f);
   close(g);
end.