#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#define N_MAX 50010
#define infinity 500000

using namespace std;

int T;
int N, M, S;
int a, b, c;

int initialCost[N_MAX];
int currentCost[N_MAX];
ifstream f("distante.in");
ofstream g("distante.out");

int areEquals(int *initialCost, int *currentCost, int size) 
{
	for (int i = 1; i <= size; i++)
		if (initialCost[i] != currentCost[i])
			return false;
	return true;
}

struct LessThan
{
	bool operator()(const pair<int,int>& lhs, const pair<int,int>& rhs) const
	{
		return lhs.second > rhs.second;
	}
};

void Dijkstra()
{
	vector<pair<int, int>> edges[N_MAX]; //nod, cost
	f >> N >> M >> S;
	for (int i = 1; i <= N; i++)
		f >> initialCost[i];
	
	for (int i = 1; i <= M; i++) 
	{
		f >> a >> b >> c;
		edges[a].push_back(make_pair(b, c));
	}
	
	for (int i = 1; i <= M; i++) 
	{
		currentCost[i] = infinity;
	}
	currentCost[S] = 0;

	priority_queue<pair<int, int>,vector<pair<int,int>>,LessThan> queue;
	queue.push(make_pair(S, 0));
	while (!queue.empty()) 
	{
		pair<int, int> top = queue.top();
		queue.pop();
		for (pair<int,int> it : edges[top.first])
		{
			if (currentCost[it.first] > currentCost[top.first] + it.second)
			{
				currentCost[it.first] = currentCost[top.first] + it.second;
				queue.push(make_pair(it.first, currentCost[it.first]));
			}
		}
	}
	if (areEquals(initialCost, currentCost, N))
		g << "DA\n";
	else g << "NU\n";
}

int main() {
	f >> T;
	for (int i = 0; i < T;i++)
		Dijkstra();
	f.close();
	g.close();
	return 0;
}