#include <stdio.h>
#include <values.h> 
#define Nmax 50001

struct graf { int nod, cost; graf * next; } * g[Nmax];
int d[Nmax], h[Nmax], poz[Nmax], D[Nmax];
int nrH, n, m, s, i, T;

void readData();
void dijkstra(int);
void upheap(int);
void downheap(int);
inline void swap(int x, int y) { poz[h[x]]=y; poz[h[y]]=x; int temp=h[x]; h[x]=h[y]; h[y]=temp; }

int main()
{
	freopen("distante.in", "r", stdin);
	freopen("distante.out", "w", stdout);
	for (scanf("%d\n", &T); T; T--)
	{
		readData();
		dijkstra(s);
		for (i=1; i<=n; i++)
			if ((d[i]==MAXINT?0:d[i])!=D[i])
				{ printf("NU\n"); break; }
		if (i>n) printf("DA\n");
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

void dijkstra(int s)
{
	int x;
	for (i=1; i<=n; i++) { d[i]=MAXINT; poz[i]=0; } nrH=0;
	h[++nrH]=s; d[s]=0; poz[s]=1;
	while (nrH)
	{
		x=h[1];
		swap(1,nrH);
		nrH--;
		downheap(1);
		for (graf * p = g[x]; p; p=p->next)
		{
			if (d[p->nod] > d[x] + p->cost)
			{
				d[p->nod] = d[x] + p->cost;
				if (poz[p->nod]) upheap(poz[p->nod]);
				else
				{
					h[++nrH]=p->nod;
					poz[h[nrH]]=nrH;
					upheap(nrH);
				}
			}
		}
	}
}

void upheap(int loc)
{
	if (loc==1) return;
	int tata = loc>>1;
	if (d[h[tata]] > d[h[loc]]) { swap(tata,loc); upheap(tata); }
}

void downheap(int loc)
{
	int fiu;
	if (loc << 1 <= nrH) 
	{
		fiu=loc<<1;
		if (fiu+1 <= nrH && d[h[fiu+1]]<d[h[fiu]]) fiu++;
	}
	else return;
	if (d[h[loc]] > d[h[fiu]]) { swap(loc,fiu); downheap(fiu); }
}

void readData()
{

	graf * q;
	for (i=1; i<=n; i++)
		for (; g[i]; q=g[i], g[i]=g[i]->next, delete q);
	int x, y, z;
	scanf("%d %d %d\n", &n, &m, &s);
	for (i=1; i<=n; i++) scanf("%d ", &D[i]);
	for (; m; m--)
	{
		scanf("%d %d %d\n", &x, &y, &z);
		graf * q = new graf;
		q->nod=y; q->cost=z; q->next = g[x]; g[x] = q;
		q=new graf;
		q->nod=x; q->cost=z; q->next = g[y]; g[y] = q;
	}
}