#include<stdio.h>
#define N 50001
#define M 100001
int rez[N],d[N];
const int oo = 2000000000;
int n,m,*a[N],*a1[N],h[M],p[N],nh;
char s[50];
struct consturi{int x,y,z;}c[M];
inline void schimb(int &x,int &y)
{
	int aux=x;
	x=y;
	y=aux;
}

void coboara(int p)
{
	int pmin=p;
	if(2*p<=nh && d[h[2*p]] < d[h[pmin]])
		pmin=2*p;
	if(2*p+1<=nh && d[h[2*p+1]] < d[h[pmin]])
		pmin=2*p+1;
	if(pmin!=p)
	{
		schimb(h[p],h[pmin]);
		coboara(pmin);
	}
}

void urca(int p)
{
	while(p>=2 && d[h[p/2]] > d[h[p]])
	{
		schimb(h[p],h[p/2]);
		p/=2;
	}
}
int minim()
{
	int aux=h[1];
	schimb(h[1],h[nh--]);
	coboara(1);
	return aux;
}
void update(int x)
{
	for (int i=1; i<=a[x][0]; ++i)
	{
		int y=a[x][i],c=a1[x][i];
		if (d[x]+c<d[y])
		{
			d[y]=d[x]+c;
			h[++nh]=y;
			urca(nh);
		}
	}
}
void dijkstra(int x0)
{
	for (int i=1; i<=n; ++i)
		d[i]=oo;
	d[x0]=0;
	h[++nh]=x0;
	while(nh)
	{
		int x=minim();
		update(x);
	}
}
void parsare(int k)
{
	int nr=0,num=0;
	for (int i=0; s[i]&&s[i]!='\n'; ++i)
	{
		while (s[i]>='0'&&s[i]<='9'&&s[i]&&s[i]!='\n')
		{
			nr=nr*10+s[i]-'0';
			++i;
		}
		++num;
		if (num==1) c[k].x=nr;
		else
			if (num==2) c[k].y=nr;
		else
			if (num==3) c[k].z=nr;
		nr=0;
	}
}
bool verific()
{
	for (int i=1; i<=n; ++i)
		if (rez[i]!=d[i])
			return false;
		return true;
}
void citire()
{
	freopen("distante.in","r",stdin);
	freopen("distante.out","w",stdout);
	short int t;
	scanf("%hd",&t);
	while (t--)
	{
		int nod;
		scanf("%d%d%d",&n,&m,&nod);
		for (int i=1; i<=n; ++i)
			scanf("%d",&rez[i]);
		scanf("\n");
	for (int i=1; i<=m; ++i)
	{
		gets(s);
		parsare(i);
		h[i]=i;
		++d[c[i].x];
		++d[c[i].y];
	}
	for (int i=1; i<=n; ++i)
	{
		a[i]=new int [1+d[i]];
		a[i][0]=0;
		a1[i]=new int [1+d[i]];
		a1[i][0]=0;
	}
	for (int i=1; i<=m; ++i)
	{
		a[c[i].x][++a[c[i].x][0]]=c[i].y;
		a1[c[i].x][++a1[c[i].x][0]]=c[i].z;
	}
	dijkstra(nod);
	if (verific())
		printf("DA\n");
	else
		printf("NU\n");
	}
}


int main()
{
	citire();
	return 0;
}