#include<stdio.h>
FILE *f,*g;
int test,i; long n,m,sursa,j,d[50005],nr,x,y,z,dd,c[50005],t[4][200006],v,a,s[75005],ss[75000],k,dist[50005],ok;
int main()
{ f=fopen("distante.in","r"); g=fopen("distante.out","w");
  fscanf(f,"%d",&test);
  for(i=1;i<=test;i++)
   { fscanf(f,"%ld%ld%ld",&n,&m,&sursa);
     for(j=1;j<=n;j++) fscanf(f,"%ld",&d[j]); nr=1;
     for(j=1;j<=m;j++)
      { fscanf(f,"%ld%ld%ld",&x,&y,&z);
	if(!c[x])
	 { while(t[1][nr]!=0) nr++;
	   c[x]=nr; t[1][nr]=y; t[3][nr]=z;
	 }
	else
	 { v=c[x];
	   while(t[2][v]!=0) v=t[2][v];
	   while(t[1][nr]!=0) nr++;
	   t[2][v]=nr; t[1][nr]=y; t[3][nr]=z;
	 }
	a=x; x=y; y=a;
	if(!c[x])
	 { while(t[1][nr]!=0) nr++;
	   c[x]=nr; t[1][nr]=y; t[3][nr]=z;
	 }
	else
	 { v=c[x];
	   while(t[2][v]!=0) v=t[2][v];
	   while(t[1][nr]!=0) nr++;
	   t[2][v]=nr; t[1][nr]=y; t[3][nr]=z;
	 }
      }
     dd=1; s[1]=sursa; k=0;
     for(j=1;j<=n;j++) dist[j]=-1; dist[sursa]=0;
     while(dd!=0)
      { for(j=1;j<=dd;j++)
         { v=s[j]; v=c[v];
	   while(v!=0)
	    { if(dist[t[1][v]]==-1||dist[s[j]]+t[3][v]<dist[t[1][v]])
	       { dist[t[1][v]]=dist[s[j]]+t[3][v];
		 k++; ss[k]=t[1][v];
	       }
	      v=t[2][v];
	    }
	 }
	for(j=1;j<=k;j++) s[j]=ss[j]; dd=k; k=0;
      }
     ok=1;
     for(j=1;j<=n&&ok;j++) if(d[j]!=dist[j]) ok=0;
     if(ok) fprintf(g,"DA\n"); else fprintf(g,"NU\n");
   }
  fclose(g);
  return 0;
}