#include <queue>
#include <functional>
#include <fstream>
#include <vector>

using namespace std;

fstream fin("distante.in", ios::in);
fstream fout("distante.out", ios::out);

#define INF 0x3f3f3f3f
#define MAXN 50005
vector <pair<int, int>> list[MAXN];
int dist[MAXN], my_dist[MAXN];

class compare
{
public:
	bool operator() (int x, int y){
		return dist[x] > dist[y];
	}
};
priority_queue <int, vector<int>, compare> heap;

void read(int &n, int &s)
{
	int m, x, y, c;
	fin >> n >> m >> s;
	for (int i = 1; i <= n; i++)  fin >> my_dist[i];

	for (int i = 1; i <= m; i++)
		fin >> x >> y >> c,
		list[x].push_back(make_pair(y, c)),
		list[y].push_back(make_pair(x, c));

	fin.close();
}
void dijkstra(int n, int start){
	for (int i = 1; i <= n; i++)  dist[i] = INF;
	dist[start] = 0;
	heap.push(start);

	while (!heap.empty()){
		int node = heap.top();
		heap.pop();

		while (!list[node].empty()){
			if (dist[list[node].back().first] > dist[node] + list[node].back().second)
				dist[list[node].back().first] = dist[node] + list[node].back().second,
				heap.push(list[node].back().first);
			list[node].pop_back();
		}
	}
}
bool check(int n)
{
	for (int i = 1; i <= n; i++)
		if (dist[i] != my_dist[i])  return false;
	return true;
}

int main() 
{
	int T;
	fin >> T;

	for (int i = 1; i <= T; i++){
		int n, s;

		read(n, s);
		dijkstra(n, s);
		if (check(n))  fout << "DA\n";
		else fout << "NU\n";
	}

	fout.close();
	return 0;
}