#include<iostream>
#include<fstream>
#define NMax 50001

using namespace std;

typedef struct nod {
					int cost;
					long varf;
					struct nod *urm;
				   } Nod;

ifstream fin("distante.in");
ofstream fout("distante.out");

int t;

//listele de adiacenta pentru un graf neorientat
Nod *a[NMax];
bool exista_predecesor[NMax];


void initializare( int nr )
{
	long i;
	for ( i = 1; i <= nr; i++ )
	{
		a[i] = new Nod;
		a[i]->urm = NULL;
		exista_predecesor[ i ] = false;
	}
}

void dealocare( Nod *x )
{
	if ( x->urm != NULL )
		dealocare( x->urm );
	delete x;
}

void adauga( long x, long y, int c )
{
	Nod *nou, *ultim;
	
	ultim = a[x];
	while ( ultim -> urm )
		ultim = ultim -> urm;
		
	nou = new (Nod);
	nou->varf = y;
	nou->cost = c;
	nou->urm = NULL;
	ultim->urm = nou;
}

bool verifica ( )
{
	long d[NMax];
	long n, s, x, y, c;
	long i, j, m;
	Nod *l;

	fin >> n >> m >> s;
	initializare( n );

	for ( i = 1; i <= n; i++ )
		fin >> d[i];

	if ( d[s] > 0 )
		return false;

	for ( i = 1; i <= m; i++ )
	{
		fin >> x >> y >> c;
		
		adauga( x, y, c );
		adauga( y, x, c );
	}

	for ( i = 1; i <= n; i++ )
	{
		l = a[i];
		while ( l->urm != NULL )
		{
			if ( (l->urm)->varf != s )
			{
				if ( d[i] + (l->urm)->cost == d[(l->urm)->varf] )
					exista_predecesor[(l->urm)->varf] = true;
				else if ( d[i] + (l->urm)->cost < d[(l->urm)->varf] )
				{
					for ( j = 1; j <= n; j++ )
						dealocare( a[j] );
					return false;
				}
			}
			l = l->urm;
		}
	}

	for ( i = 1; i <= n; i++ )
		dealocare( a[i] );

	for ( i = 1; i <= n; i++ )
		if ( !exista_predecesor[i] && i != s )
			return false;
	
	return true;
}


int main()
{
	int i;
	bool ok;
	
	fin >> t;
	for ( i = 1; i <= t; i++ )
	{
		ok = verifica();
		if ( ok )
			fout << "DA" << endl;
		else
			fout << "NU" << endl;
	}

	return 0;
}