#include<fstream>
using namespace std;
ifstream f ("distante.in");
ofstream g ("distante.out");
struct nod { long x,y,c; };
nod a[100000];
long q, d[50000],i,corect[50000],m,n;
int ok,gata,nodsursa,nrgraf;
int main ()
{
	f>>nrgraf;
	for ( q=1; q<=nrgraf; q++ )
	{
		f>>n>>m>>nodsursa;
		for ( i=1; i<=n; i++ )
			f>>corect[i];
		for ( i=1; i<=m; i++ )
		{
			f>>a[i].x>>a[i].y>>a[i].c;
			if ( a[i].x==nodsursa )
				d[a[i].y]=a[i].c;
		}
		for ( i=1; i<=n; i++ )
			if ( d[i]==0 )
				d[i]=32000;
		gata=0;
		while ( !gata )
		{
			gata=1;
			for ( i=1; i<=m; i++ )
			if ( d[a[i].y]>d[a[i].x]+a[i].c )
			{ 
				gata=0;
				d[a[i].y]=d[a[i].x]+a[i].c;
			}
		}
		ok=1;
		for ( i=1; i<=n; i++ )
			if ( d[i]<32000 )
			{
				if ( corect[i]!=d[i] )
					ok=0;
			}
			else
				if ( corect[i]!=0 )
					ok=0;
		if ( ok==0 )
			g<<"NU";
		else
			g<<"DA";
		g<<endl;
		
		for ( i=1; i<=n; i++ )
			d[i]=0;
		for ( i=1; i<=m; i++ )
		{
			a[i].x=0;
			a[i].y=0;
			a[i].c=0;
		}
	}
}