#include <stdio.h>
#define DIM 500005
#define INF 123456789

struct nod {int x,ct;
			nod *urm;} *lst[DIM];
int c[DIM],h[DIM],poz[DIM], cost[DIM];
int n,m,l,t,start;

void add (int a,int b,int c)
{
	nod *p=new nod;
	p->x=b;
	p->ct=c;
	p->urm=lst[a];
	lst[a]=p;
}

void read ()
{
	int i,x,y,z;
	scanf ("%d%d%d",&n,&m,&start);
	for (i=1; i<=n; ++i)
		scanf("%d",&cost[i]);
	for (i=1; i<=m; ++i)
	{
		scanf ("%d%d%d",&x,&y,&z);
		add (x,y,z);
		add (y,x,z);
	}
}

void init ()
{
	int i;
	poz[start]=1;
	for (i=1; i<=n; ++i)
    	if (i!=start)
		c[i]=INF;
    	else c[i]=0;
}

void swap (int &a,int &b)
{
	int aux=a;
	a=b;
	b=aux;
}

void upheap (int nod)
{
	if (nod<=1) return;
	if (c[h[nod]]<c[h[nod/2]])
		{
			swap(h[nod],h[nod/2]);
			swap(poz[h[nod]],poz[h[nod/2]]);
			upheap(nod/2);
		}
}

void downheap (int nod)
{
	int min=nod;
	if (2*nod<=l) if (c[h[nod*2]]<c[h[min]]) min=2*nod;
	if (2*nod+1<=l) if (c[h[2*nod+1]]<c[h[min]]) min=2*nod+1;
	if (min!=nod)
		{
		swap(h[nod], h[min]);
		swap(poz[h[nod]],poz[h[min]]);
		downheap(min);
		}
}

void solve ()
{
	nod *p;
	int i,min;
	for (h[++l]=start; l; )
	{
		min=h[1];
		h[1]=h[--l];
		poz[h[1]]=1;
		downheap (1);
		for (p=lst[min]; p; p=p->urm)
			if (c[p->x]>c[min]+p->ct)
			{
				c[p->x]=c[min]+p->ct;
				if (poz[p->x])
					upheap (poz[p->x]);
				else
				{
					poz[h[++l]=p->x]=l;
					upheap (l);
				}
			}
	}
}

void print ()
{
	int i, ok=0;
	for (i=1; i<=n; ++i)
		if (c[i]!=cost[i]) ok=1;
	if (ok) printf("NU\n");
	else printf("DA\n");
}

int main ()
{
	freopen ("distante.in","r",stdin);
	freopen ("distante.out","w",stdout);
	scanf("%d",&t);
	for (int i=1; i<=t; ++i)
		{
			read ();
			init ();
			solve ();
			print ();
		}
	return 0;
}