#include<stdio.h>

long long i,j,k=1,d[100001],t,a[50001][50001],s[50001],n,m,p,min,l,aux[100001],_a,_b,_c,ok;
void drum(long i);
int main()
{	freopen("distante.in","r",stdin);
	freopen("distante.out","w",stdout);
	scanf("%ld",&t);
	for(l=1;l<=t;l++)
	{	scanf("%ld%ld%ld",&n,&m,&p);
		for(i=1;i<=n;i++)
			scanf("%ld",&aux[i]);
		for(i=1;i<=m;i++)
		{	scanf("%ld%ld%ld",&_a,&_b,&_c);
			a[_a][_b]=a[_b][_a]=_c;
		}
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(i!=j&&a[i][j]==0) a[i][j]=100001;
		for(i=1;i<=n;i++)
			d[i]=a[p][i];
		s[p]=1;
		for(i=1;i<=n-1;i++)
		{	min=100001;
			for(j=1;j<=n;j++)
				if(s[j]==0)
					if(d[j]<min)
					{min=d[j];k=j;}
			s[k]=1;
			for(j=1;j<=n;j++)
				if(s[j]==0)
					if(d[j]>d[k]+a[k][j])
						d[j]=d[k]+a[k][j];
		}ok=1;
		for(i=1;i<=n&&ok;i++)
			if(d[i]!=aux[i]) ok=0;
		if(!ok)	printf("%s","NU\n");
		else	printf("%s","DA\n");
		for(i=1;i<=n;i++)
		{	aux[i]=d[i]=s[i]=0;
			for(j=1;j<=n;j++)
				a[i][j]=0;
		}k=1;
	}
	return 0;
}