#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

#define INF 0x3f3f3f3f
#define mp make_pair
#define pb push_back

void read();
void Bellman_Ford(int root);

queue<int > Q;
vector< vector< pair<int, int> > > a;
int n, m, root, T;
bool s[50002];
int sol[50002], d[50002];

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

void read()
{
	ifstream fin("distante.in");
	ofstream fout("distante.out");
	
	int j;
	
	fin >> T;
	for(int i = 1; i <= T; ++i)
	{
		a.clear();
		fin >> n >> m >> root;
		a.resize(n + 1);
		
		for(j = 1; j <= n; ++j)
			fin >> sol[j];
		
		int x, y, z;
		for(j = 1; j <= m; ++j)
		{
			fin >> x >> y >> z;
			a[x].pb( mp(y, z) );
			a[y].pb( mp(x, z) );
		}
		
		Bellman_Ford(root);
		for(j = 1; j <= n; ++j)
			if( sol[j] != d[j] )
				j = n + 5;
			
			if( j != n + 6 )
				fout << "DA" << '\n';
			else
				fout << "NU" << '\n';
			
			//memset(s, 0, n + 1);
		
	}
}

void Bellman_Ford(int root)
{
	Q.push(root);
	for(int i = 1; i <= n; ++i) d[i] = INF;
	d[root] = 0;
	//s[x] = 1;
	
	while( !Q.empty() )
	{
		int k = Q.front();
		Q.pop();
		vector<pair<int, int> >::iterator it = a[k].begin(), sf = a[k].end();
		
		for( ; it != sf; ++it)
			if( d[ it->first] > d[ k ] + it -> second )
			{
				d[ it->first] = d[ k ] + it -> second;
				Q.push( it -> first );
			}
	}
				
}