#include<fstream>
#define DIM 200000
#define INF 99999999
using namespace std;
int S,N,M,K,i,I,B[DIM],D2[DIM],ok,is,ic,C[DIM],D[DIM];

struct nod{
	int inf,dist;
	nod* adr;
}*A[DIM],*p,*q;
ifstream f("distante.in");
ofstream g("distante.out");

void citire(){
	int a,b,d;
	f>>N>>M>>S;
	for(i=1;i<=N;i++)
		f>>D2[i];
	for(i=1;i<=M;i++){
		
		f>>a>>b>>d;
		p=new nod;
		p->inf=b;
		p->dist=d;
		p->adr=A[a];
		A[a]=p;
		q=new nod;
		q->inf=a;
		q->dist=d;
		q->adr=A[b];
		A[b]=q;
	}


}
void afisare(){
for(i=1;i<=N;i++)
	{	p=A[i];
		while(p)
		{
			g<<p->inf<<" ";
			p=p->adr;
		}
		g<<"\n";
	}
}
int main (){
	f>>K;
	for(I=1;I<=K;I++)
	{
		citire();
		//afisare();
		for(i=1;i<=N;i++)
			if(i!=S)
				D[i]=INF;
		
		
		
		ic=is=1;	
		B[S]=1;
		C[ic]=S;
		while(ic<=is)
		{
			B[C[ic]]=0;
			p=A[C[ic]];
			for(;p;p=p->adr)
			{
				if(D[p->inf]>D[C[ic]]+p->dist)
				{
					D[p->inf]=D[C[ic]]+p->dist;
					if(B[p->inf]==0)
					{
						B[p->inf]=1;
						C[++is]=p->inf;
					}				
				}	
			}
		
			ic++;
		}
		D[S]=0;
		for(i=1;i<=N;i++)
			if(D[i]==INF)
				D[i]=0;
				
		
		ok=1;
		for(i=1;i<=N;i++)
			if(D2[i]!=D[i])
			{
				ok=0;
				break;
			}
			if(!ok)
				g<<"NU\n";
			else
				g<<"DA\n";
	}
return 0;
}