#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

#define INF INT_MAX/2-1
#define NMAX 50000
#define MMAX 100000

struct muchie{unsigned short a,b,c;};

muchie v[MMAX+1],w[MMAX+1];
int pv[NMAX+1],pw[NMAX+1];
//int c[NMAX+1][NMAX+1];

void poz(int li,int ls,int&piv,muchie e[]){
int i=li,j=ls,d=0;
muchie t;
while(i<j){
	if(e[i].a>e[j].a){
		t=e[i];e[i]=e[j];e[j]=t;d=1-d;
		}
	i+=d;j-=1-d;
	}
piv=i;
}
void qsrt(int st,int dr,muchie e[]){
int piv;
if(st<dr){
	poz(st,dr,piv,e);
	qsrt(st,piv-1,e);
	qsrt(piv+1,dr,e);
	}
}

int main(){
freopen("distante.in","r",stdin);
freopen("distante.out","w",stdout);
int n,m,i,j,k,t,nrt,ok,nrsel,gata,min;
int o[NMAX+1]={0},d[NMAX+1]={0};
char sir1[4*NMAX],sir[31],*p;
unsigned short s[NMAX+1]={0},x,y,z,start,pz;
scanf("%d",&t);
for(nrt=0;nrt<t;++nrt){
	scanf("%d%d%hu\n",&n,&m,&start);
	fgets(sir1,4*NMAX,stdin);
	p=sir1;
	for(i=1;i<=n;++i){
		o[i]=atoi(p);
		while(*p!=32)++p;++p;
		}
	for(i=1;i<=m;++i){
		fgets(sir,30,stdin);p=sir;
		x=atoi(p);
		while(*p!=32)++p;++p;
		y=atoi(p);
		while(*p!=32)++p;++p;
		z=atoi(p);
		v[i].a=x,v[i].b=y,v[i].c=z;
		w[i].a=y,w[i].b=x,w[i].c=z;
		}
	qsrt(1,m,v);
	qsrt(1,m,w);
	for(i=1;i<=n;++i) c[i][i]=0;
	for(i=1;i<=m;++i){
		pz=v[i].a;
		if(!pv[pz]) pv[pz]=i;
		}
	for(i=1;i<=m;++i){
		pz=w[i].a;
		if(!pw[pz]) pw[pz]=i;
		}

	for(i=1;i<=n;++i) {d[i]=INF;s[i]=0;}
	d[start]=0;
	i=pv[start];
	if(i)
	while(i<=m&&v[i].a==start){
		pz=v[i].b;
		d[pz]=v[i].c;
		++i;
		}
	i=pw[start];
	if(i)
	while(i<=m&&w[i].a==start){
		pz=w[i].b;
		d[pz]=w[i].c;
		++i;
		}

	s[start]=1;nrsel=1;
	gata=0;k=0;
	int imin,ales,umin,sum;
	imin=1;umin=0;
	do{
		min=INF+INF;
		ales=0;
		for(i=imin;i<=n;++i)
			if(!s[i]){
				if(!ales) imin=i,ales=1;
				if(d[i]<min){
				min=d[i];k=i;
				if(min=umin) break;
				}
			}
		umin=d[k];
		nrsel++;
		if((d[k]==INF||nrsel==n)) gata=1;
		else{
			s[k]=1;
			i=pv[k];
			if(i)
			while(i<=m&&v[i].a==k){
				pz=v[i].b;
				if(!s[pz]){
					sum=d[k]+v[i].c;
					if(d[pz]>sum)
						d[pz]=sum;
					}
				++i;
				}
			i=pw[k];
			if(i)
			while(i<=m&&w[i].a==k){
				pz=w[i].b;
				if(!s[pz]){
					sum=d[k]+w[i].c;
					if(d[pz]>sum)
						d[pz]=sum;
					}
				++i;
				}
			}
		}while(!gata);

	for(i=1;i<=n;++i)
		if(d[i]==INF) d[i]=0;
	ok=1;
	for(i=1;i<=n&&ok;++i) ok=d[i]==o[i];
	ok?printf("DA\n"):printf("NU\n");
	}
return 0;
}