#include <stdio.h>
#include <iostream.h>
#include <fstream.h>

const int pinf=2147483647;
const int NMAX=50010;

ofstream g("distante.out");

struct nod{
	nod *urm;
	int cost,nd;

} *p[NMAX],*aux,*auxx;

int dd[NMAX],n,m,x,y,c,s[NMAX],k,min,j,gasit;
int dim_heap,poz[NMAX],dbronzarel[NMAX];

struct frunza{int cost,nod; } d[NMAX];

inline int parinte(int i) {return i/2;}
inline int stanga(int i) {return 2*i;}
inline int dreapta(int i) {return 2*i+1;}

void reconstituie_heap(int i){
	 int minim,t;
	 int st=stanga(i);
	 int dr=dreapta(i);

	 if (st<=dim_heap && d[i].cost>d[st].cost) {minim=st;}
	 else minim=i;
	 if (dr<=dim_heap && d[dr].cost<d[minim].cost) {minim=dr;}

	 if (minim!=i) {
					poz[d[i].nod]=minim;
					poz[d[minim].nod]=i;

					t=d[i].cost, d[i].cost=d[minim].cost,d[minim].cost=t;
					t=d[i].nod, d[i].nod=d[minim].nod, d[minim].nod=t;

					reconstituie_heap(minim);
				   }

	 }

int extrage_min(){
	if (dim_heap<1) return -1;
	else{
	int pz=d[1].nod;min=d[1].cost;
	d[1].cost=d[dim_heap].cost;
	d[1].nod=d[dim_heap].nod;
	dim_heap--;
	reconstituie_heap(1);
	return pz;
	}
}


void insereaza_in_heap(frunza element ){
	 int i;
	 dim_heap++;i=dim_heap;

	 while(i>1 && element.cost<d[parinte(i)].cost) {poz[d[parinte(i)].nod]=i; d[i].cost=d[parinte(i)].cost; d[i].nod=d[parinte(i)].nod; i=parinte(i);}

	 d[i].cost=element.cost;
	 d[i].nod=element.nod;

	 poz[d[i].nod]=i;

	 }

void update_heap(frunza element){
	int i=poz[element.nod];


	while(i>1 && element.cost<d[parinte(i)].cost) {poz[d[parinte(i)].nod]=i; d[i].cost=d[parinte(i)].cost; d[i].nod=d[parinte(i)].nod; i=parinte(i); }

	d[i].cost=element.cost;
	d[i].nod=element.nod;

	poz[d[i].nod]=i;

	}

int main()
{   int pz,sursa,i;
	frunza auxx;
	int auxiliar,teste,contor;

	freopen("distante.in","r",stdin);
	//freopen("distante.out","w",stdout);
	scanf("%d",&teste);
	for(contor=1;contor<=teste;contor++){
	scanf("%d%d%d",&n,&m,&sursa);
	for(i=1;i<=n;i++) scanf("%d",&dbronzarel[i]);
//	sursa=1;
	for(i=1;i<=n;i++) dd[i]=pinf;
	for(i=1;i<=n;i++) s[i]=0;
	/*auxiliar=extrage_min();
        while(auxiliar!=-1) auxiliar=extrage_min();*/
	for(i=1;i<=m;i++){
 		scanf("%d%d%d",&x,&y,&c);
		aux=new nod;
		aux->urm=p[x];
		aux->nd=y,aux->cost=c;
		p[x]=aux;
		if (x==sursa) {dd[y]=c;auxx.cost=c,auxx.nod=y; insereaza_in_heap(auxx);}
	}

	s[sursa]=1;

	for(i=1;i<=n && dim_heap!=0;i++){
		if (i!=sursa){
		pz=extrage_min();
		if (pz!=-1){
		s[pz]=1;
		for(aux=p[pz];aux!=NULL;aux=aux->urm)
		 if(!s[aux->nd])
		 {	if (dd[aux->nd]>dd[pz]+aux->cost){
				auxx.nod=aux->nd, auxx.cost=dd[pz]+aux->cost;
				if (dd[aux->nd]==pinf) insereaza_in_heap(auxx);
				else update_heap(auxx);
				dd[aux->nd]=dd[pz]+aux->cost;}
		 }
		}
		}

	}

	/*for(i=2;i<=n;i++)
	 if (dd[i]==pinf) printf("0 ");
	 else printf("%d ",dd[i]);*/


	int ok=1;
	for(i=1;i<=n && ok;i++)
	 if (dd[i]==pinf) {if (dbronzarel[i]==0) ok=1; else ok=0;}
	 else if (dd[i]!=dbronzarel[i]) ok=0;

	if (ok==0) g<<"NU";
	else g<<"DA";
	if (contor<teste) g<<endl;

	for(i=1;i<=n;i++) dd[i]=pinf;
	for(i=1;i<=n;i++) s[i]=0;


	for(i=1;i<=n;i++) p[i]=NULL;
	


	}
	g.close();
	return 0;
}