#include<fstream.h>
ifstream f("distante.in");
ofstream g("distante.out");
long viz[50010],n,m,d[50010],t,s,d1[50010];
struct coada
{
long inf;
coada *urm;
}*c,*ultim;

struct elem
{
long inf;
int cost;
elem *urm;
}*a[50010];
void citire()
{
int x,y,co,i;
elem *p;
f>>n>>m>>s;
for(i=1;i<=n;i++)
	f>>d1[i];
for(i=0;i<m;i++)
	{
	f>>x>>y>>co;
	p=new elem;
	p->inf=y;
	p->cost=co;
	p->urm=a[x];
	a[x]=p;
	}

}

void prima(int s)
{
 int i;
 elem *p;
 for(i=1;i<=n;i++)
 {
	d[i]=2000000000;
 }
 d[s]=0;
}

void implementare(int s)
{
 coada *q,*t;
 elem *p;
 c=new coada;
 c->inf=s;
 c->urm=NULL;
 viz[s]=1;
 ultim=c;
 while(c!=NULL)
 {

	p=a[c->inf];
	while(p!=NULL)
	{
	if(d[p->inf]>d[c->inf]+p->cost)
		{
		d[p->inf]=d[c->inf]+p->cost;
		if(viz[p->inf]==0)
			{
			q=new coada;
			viz[p->inf]=1;
			q->inf=p->inf;
			q->urm=NULL;
			ultim->urm=q;
			ultim=q;
			}
		}
	p=p->urm;
	}
 t=c;
 viz[c->inf]=0;
 c=c->urm;
 delete t;
 }

}
void afisare()
{
 int ok=1,i;
 for(i=1;i<=n;i++)
	if(d[i]!=d1[i])
		ok=0;
 if(ok==1)
	g<<"DA"<<'\n';
 else
	g<<"NU"<<'\n';
}

int main()
{
 int i;
 f>>t;
 for(i=0;i<t;i++)
 {
	 citire();
	 prima(s);
	 implementare(s);
	 afisare();
 }
 g.close();
 return 0;
}