program pascal;
var f,g:text; a:array[1..1000,1..1000] of integer;
    d,viz,dis:array[1..50000] of integer;
    min,poz,i,j,n,m,s,q,t,x,z,y:longint; ok:boolean;

  procedure completare;
  begin
  for i:=1 to n do
   for j:=1 to n do
    if i<>j then a[i,j]:=10000;
  end;

  procedure golire;
  begin
   for i:=1 to n do
          begin
          viz[i]:=0;
          d[i]:=0;
          end;
  end;

  procedure dijkstra;
  begin
  viz[s]:=1;
  for i:=1 to n do d[i]:=a[s,i];

  for i:=1 to n-1 do
    begin
    min:=10000;
    for j:=1 to n do
    if viz[j]=0 then
      if d[j]<min then
         begin
         min:=d[j];
         poz:=j;
         end;
    viz[poz]:=1;
    for j:=1 to n do
    if viz[j]=0 then
     if d[j]>d[poz]+a[poz,j] then  d[j]:=d[poz]+a[poz,j];
     end;
  end;

  procedure verificare;
  begin
  ok:=true;
  for i:=1 to n do
  if dis[i]<>d[i] then begin ok:=false; break; end;
  if ok then writeln(g,'DA')
        else writeln(g,'NU');
  end;

  procedure citire;
  begin
  assign(f,'distante.in'); reset(f);
  assign(g,'distante.out'); rewrite(g);
  readln(f,t);
  for q:=1 to t do
      begin
      readln(f,n,m,s);
      completare;
      golire;
      for i:=1 to n do read(f,dis[i]);
      for i:=1 to m do
          begin
          read(f,x,y,z);
          a[x,y]:=z;
          a[y,x]:=z;
          end;
     dijkstra;
     verificare;
     end;
  close(f);
  close(g);
  end;

begin
citire;
end.