#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 50050
#define INF 1 << 30

int cost[NMAX], C[NMAX], H[NMAX], poz[NMAX], n, m, s, t, N;
vector < pair <int, int> > G[NMAX];

void read ();
void up_heap (int);
void down_heap (int);
void delete_heap (int);
void dijkstra_heap ();
int check ();

int main () {
	
	freopen ("distante.in", "r", stdin);
	freopen ("distante.out", "w", stdout);
	
	scanf ("%d", &t);
	
	for ( ; t--; ) {
		read ();
		dijkstra_heap ();
		if (check ())
			printf ("DA\n");
		else
			printf ("NU\n");
	}
	
	return 0;
}

void read () {
	
	int i, x, y, c;
	
	scanf ("%d %d %d", &n, &m, &s);
	
	for (i = 1; i <= n; i++) {
		scanf ("%d", &cost[i]);
		G[i].clear ();
	}
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d %d", &x, &y, &c);
		G[x].push_back (make_pair (y, c));
		G[y].push_back (make_pair (x, c));
	}
}

void up_heap (int k) {
	
	int t, c, aux;
	
	t = k >> 1, c = k;
	while (t > 0 && C[H[c]] < C[H[t]]) {
		aux = H[c], H[c] = H[t], H[t] = aux;
		poz[H[c]] = c, poz[H[t]] = t;
		
		c = t, t = c >> 1;
	}
}

void down_heap (int k) {
	
	int t, c, aux;
	
	t = k, c = t << 1;
	if (c < N && C[H[c+1]] < C[H[c]])
		c++;
	
	while (c <= N && C[H[t]] > C[H[c]]) {
		aux = H[c], H[c] = H[t], H[t] = aux;
		poz[H[c]] = c, poz[H[t]] = t;
		
		t = c, c = t << 1;
		if (c < N && C[H[c+1]] < C[H[c]])
			c++;
	}
}

void delete_heap (int k) {
	
	H[k] = H[N], poz[H[k]] = k;
	N--;
	
	down_heap (k);
}

void dijkstra_heap () {
	
	int i, nod, fiu, cst;
	
	N = 0;
	for (i = 1; i <= n; i++)
		C[i] = INF, poz[i] = 0;
	
	N++;
	H[N] = s, poz[s] = 1, C[s] = 0;
	while (N) {
		nod = H[1];
		delete_heap (1);
		
		for (i = 0; i < (int) G[nod].size(); i++) {
			fiu = G[nod][i].first, cst = G[nod][i].second;
			if (C[nod] + cst < C[fiu]) {
				C[fiu] = C[nod] + cst;
				
				if (!poz[fiu]) {
					N++, H[N] = fiu, poz[fiu] = N;
					up_heap (N);
				}
				else
					up_heap (poz[fiu]);
			}
		}
	}
}

int check () {
	
	int i;
	
	for (i = 1; i <= n; i++)
		if (cost[i] != C[i])
			return 0;
	return 1;
}