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

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

struct muchie{unsigned short a,b,c;};
struct nod{unsigned v,p;};
muchie v[MMAX+1],w[MMAX+1];
int pv[NMAX+1],pw[NMAX+1];
nod c[NMAX+NMAX];
int nn;

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);
	}
}
void refac(int vf){
int par=vf,cop=vf*2,gata=0;
nod t=c[vf];
while(cop<=nn&&!gata){
	if(cop<nn&&c[cop].v>c[cop+1].v) ++cop;
	if(c[par].v>c[cop].v){
		c[par]=c[cop];par=cop;cop=2*par;
		}
	else gata=1;
	}
c[par]=t;
}
void init(){
int i;
for(i=nn/2;i>=1;--i) refac(i);
}
void elim(){
if(nn){
	c[1]=c[nn];--nn;refac(1);
	}
else c[1]=c[0];
}
void addnou(){
int cop=nn,par=cop/2;
nod t;
while(par>=1&&c[par].v>c[cop].v){
	t=c[cop];c[cop]=c[par];c[par]=t;
	cop=par;par=cop/2;
	}
}

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[5*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,5*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) pv[i]=pw[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;
		++nn;c[nn].v=d[pz];c[nn].p=pz;
		++i;
		}
	i=pw[start];
	if(i)
	while(i<=m&&w[i].a==start){
		pz=w[i].b;
		d[pz]=w[i].c;
		++nn;c[nn].v=d[pz];c[nn].p=pz;
		++i;
		}

	init();
	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];*/
		do{
			k=c[1].p;
			if(s[k]) elim();
			}while(s[k]&&k);
		if(k) elim();
		else break;
		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;
						++nn;c[nn].v=d[pz];c[nn].p=pz;
						addnou();
						}
					}
				++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;
						++nn;c[nn].v=d[pz];c[nn].p=pz;
						addnou();
						}
					}
				++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;
}