program pascal;
var a:array[0..5000,0..5000] of -3..1000;
    s,d,d1:array[0..50000] of integer;
    n,i,j,r,min,poz,m:longint;
    t,q:integer;
    f,g:text;

procedure citire;
var p,o,c:longint;
begin
   read(f,n,m,r);
   for i:=1 to n do
      read(f,d1[i]);
   for i:=1 to n do
      for j:=1 to n do
         a[i,j]:=-1;
   for i:=1 to n do
      a[i,i]:=0;
   for i:=1 to m do
      begin
         read(f,p,o,c);
         a[p,o]:=c;
         a[o,p]:=c;
      end;
end;

function identic:boolean;
begin
   identic:=true;
   for i:=1 to n do
      if d1[i]<>d[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;
         s[r]:=1;
         d[r]:=0;
         for i:=1 to n do
            if i<>r then
               if (a[r,i]<>-1) then
                  d[i]:=a[r,i]
               else
                  d[i]:=maxint;
         for i:=1 to n-1 do
            begin
               min:=maxint;
               for j:=1 to n do
                  if s[j]=0 then
                     if d[j]<min then
                        begin
                           min:=d[j];
                           poz:=j;
                        end;
               s[poz]:=1;
               for j:=1 to n do
                  if (s[j]=0)and(a[poz,j]<>-1) then
                     if d[j]>d[poz]+a[poz,j] then
                        d[j]:=d[poz]+a[poz,j];
            end;
         if identic then
            writeln(g,'DA')
         else
            writeln(g,'NU');
      end;
   close(f);
   close(g);
end.