#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define dim 50005
#define oo 1005
using namespace std;

int *A[dim],*C[dim],n,m,s,t,T,M[dim],V[dim],viz[dim],min,ok,ii,i,x,y,c;

FILE *f=fopen("distante.in","r") ,*g=fopen("distante.out","w");

void citire()
{
	fscanf(f,"%d %d %d",&n,&m,&s);

	for(i=1;i<=n;i++)
	{	
		fscanf(f,"%d",&V[i]);
		A[i]=(int *)realloc(A[i],sizeof(int));
		A[i][0]=0;	
		C[i]=(int *)realloc(C[i],sizeof(int));
		C[i][0]=0;	
		
		M[i]=oo;
	}
	
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d %d %d",&x,&y,&c);
		
		if(x!=y)
		{
		A[x][0]++;
		A[x]=(int *)realloc(A[x], (A[x][0]+1) * sizeof(int) );
		A[x][ A[x][0] ]= y;
		
		A[y][0]++;
		A[y]=(int *)realloc(A[y], (A[y][0]+1) * sizeof(int) );
		A[y][ A[y][0] ]= x;
		
		C[x][0]++;
		C[x]=(int *)realloc(C[x], (C[x][0]+1) * sizeof(int) );
		C[x][ C[x][0] ]= c;
		
		C[y][0]++;
		C[y]=(int *)realloc(C[y], (C[y][0]+1) * sizeof(int) );
		C[y][ C[y][0] ]= c;
		}	
	}

}

void djk(int d)
{
	viz[d]=1;
	
	for(i=1;i<=A[d][0];i++)
		if(!viz[A[d][i]])
		{
			if(M[ A[d][i] ] > M[d] + C[d][i])
				M[ A[d][i] ] = M[d] + C[d][i];	
		}
	min=oo; ok=0;
	for(i=1;i<=n;i++)
		if(min < M[i] && !viz[i])
			min=M[i], ii=d, ok=1;
		
	if(ok)
		djk(ii);
return ;
}

int main()
{
	
fscanf(f,"%d",&t);

for(T=1;T<=t;T++)
{
	citire();

M[s]=0; 
min=oo;

for(i=1;i<=A[s][0];i++)
	{M[A[s][i]] = C[s][i]; 
		if(M[A[s][i]] < min)
		{
		ii=A[s][i];
		min=M[A[s][i]];
		}
	}

djk(ii);
ok=1;
for(i=1;i<=n;i++)
	if(M[i]!=V[i])
	{
		fprintf(g,"NU\n");
		ok=0; 
		break;	
	}
if(ok)
	fprintf(g,"DA\n");

memset(viz,0,sizeof(viz));
memset(A,0,sizeof(A));
memset(C,0,sizeof(C));
memset(M,0,sizeof(M));

}

fclose(f);
fclose(g);

return 0;
}