#include <stdio.h>
#include <fstream.h>
#include <vector.h>
#define INF 2000000000
#define r 50001
ifstream fin("distante.in");
FILE *g=fopen ("distante.out", "w");
struct nod {  int x,c;	} t;
vector <nod> v[r];
int H[r],P[r],d[r],sol[r];
int n,m,i,S,T,k;

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

void citire() {
int i,x,y;
fin>>n>>m>>S;
for (i=1;i<=n;i++)
	fin>>sol[i];
for (i=1;i<=m;i++)
{
	fin>>x>>y>>t.c;
	t.x=y;	v[x].push_back(t);
//	t.x=x;	v[y].push_back(t);
}
}

void initializare()
{
for (int i=1;i<=n;i++)
		d[i]=INF,	P[i]=-1;
}

void downheap(int x) {
int fiu;
do
{
	fiu=0;
	if (2*x<=k)									fiu=2*x;
	if (2*x+1<=k && d[H[fiu]] > d[H[fiu+1]])	fiu=2*+1;
	if (d[H[fiu]] > d[H[x]])					fiu=0;
	
	if (fiu)
	{
		swap (H[fiu], H[x]);
		P[H[fiu]]=fiu;
		P[H[x]]=x;
		x=fiu;
	}
}
while (fiu);
}
	
void upheap(int x) {
	while (x>1 && d[H[x]]<d[H[x/2]])
	{
		swap (H[x], H[x/2]);
		P[H[x]]=x;
		P[H[x/2]]=x/2;
		x/=2;
	}
}

void dijkstra() {
int min,i;
initializare();
d[S]=0;		P[S]=1;		k=0;	H[++k]=S;

while (k)
{
	min=H[1];
	
	swap(H[1], H[k--]);	
	P[H[1]]=1;
	downheap(1);
	
	for (i=0;i<v[min].size();i++)
		if (d[v[min][i].x] > d[min] + v[min][i].c)
		{
			d[v[min][i].x] = d[min] + v[min][i].c;
			if (P[v[min][i].x]!=-1)
				upheap(P[v[min][i].x]);
			else
			{
				H[++k]=v[min][i].x;
				P[H[k]]=k;
				upheap(k);
			}
		}
}

}

int valid() {
for (int i=1;i<=n;i++)
	if (sol[i]!=d[i])
		return 0;
return 1;
}
	
int main() {
fin>>T;
for (i=1;i<=T;i++)
{
	citire();
	dijkstra();
	if ( valid() )	fprintf (g, "DA\n");
	else			fprintf (g, "NU\n");
}

return 0;
}