#include<stdio.h>
#include<fstream.h>

long a[50000][50000],n,m,d[50000],s[50000],MAXLONG=32000,sal[50000],S;
int t;
ifstream f("distante.in");
ofstream g("distante.out");

void init ()
{
	long i,j;
	for (i=1;i<=n;++i)
	{
		d[i]=MAXLONG;
		for (j=1;j<=n;++j)
			a[i][j]=MAXLONG;
	}
}

void read ()
{
	f>>n>>m>>S;
	init ();
	long i,x,y,c;
	for(i=1;i<=n;i++)
		f>>sal[i];
	for (i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		a[x][y]=c;
	}
}

void solve ()
{
	long i,j,min,poz;
	s[S]=1;
	for (i=1;i<=n;++i)
		if (a[S][i]<MAXLONG)
		{
			d[i]=a[S][i];
			//t[i]=1;
		}
	for (i=1;i<=n-1;++i)
	{
		min=MAXLONG;
		for (j=1;j<=n;++j)
			if (d[j]<min && !s[j])
			{
				min=d[j];
				poz=j;
			}
		s[poz]=1;
		for (j=1;j<=n;++j)
			if (!s[j] && a[poz][j]!=MAXLONG && d[j]>d[poz]+a[poz][j])
			{
				d[j]=d[poz]+a[poz][j];
				//t[j]=poz;
			}
	}
}

void write ()
{
	long i;
	int ok=1;
	for (i=1;i<=n;i++)
	{
		if(i==S)
		{
			d[i]=0;
		}
		if(sal[i]!=d[i])
			ok=0;
		
	}
	
	if(ok==1)
		g<<"DA\n";
	else
		g<<"NU\n";
		
}

int main ()
{
	f>>t;
	for(int i=1;i<=t;i++)
	{
		read ();
		solve ();
		write ();
	}
	f.close();
	g.close();
	return 0;
}