#include<stdio.h>
#define INF 1000000000
long A[5000][5000],x,y,c,i,C[50000],m,s,nod,min,n,t,V[100],B[100],teste,k;
int main()
{
freopen("distante.in","r",stdin);
freopen("distante.out","w",stdout);
scanf("%ld",&teste);
for (k=1;k<=teste;k++)
	{
	scanf("%ld%ld%ld",&n,&m,&s);
	for (i=1;i<=n;i++)
		scanf("%ld",&B[i]);
	min=INF;
	for (i=1;i<=n;i++)
		{
		scanf("%ld%ld%ld",&x,&y,&c);
		A[x][y]=c;
		}
	for (i=1;i<=n;i++)
		{
		V[i]=0;
		C[i]=INF;
		}
	C[s]=0;
	t=0;
	while (!t)
		{
		t=1;
		min=INF;
		for (i=1;i<=n;i++)
			if (C[i]<min&&V[i]!=1)
				{
				min=C[i];
				nod=i;
				t=0;
				}
		V[nod]=1;
		for (i=1;i<=n;i++)
			if (C[nod]+A[nod][i]<C[i]&&A[nod][i]!=0)
				C[i]=C[nod]+A[nod][i];
		}
	t=1;
	for (i=1;i<=n;i++)
		if (C[i]!=B[i])
			{
			printf("%c%c",'N','U');
			t=0;
			break;
			}
	if (t)
		printf("%c%c",'D','A');
	printf("%c",'\n');
	}
return 0;
}