#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define mp make_pair
#define pb push_back
#define N 50100
#define ls(st) st << 1
#define F first 
#define S second 
#define INF 0x3f3f3f3f


vector < pair <int, int> > a[N];
int n, m, k, t, s, d2[N], poz[N], h[N], d[N];

void citire(), dijkstra(), rezolva();

int main(){
	freopen("distante.in","r",stdin);
	freopen("distante.out","w",stdout);
	scanf("%d", &t);
	for ( ;t; --t) rezolva();
	
	return 0;
}

void citire(){
int i, x, y, z;
	scanf("%d %d %d", &n, &m, &s);
	
	for (i = 1; i <= n; i++){
		scanf("%d", &d2[i]);
		a[i].clear();
	}
	
	for (i = 1; i <= m; ++i){
		scanf("%d %d %d", &x, &y, &z);
		a[x].pb(mp(y,z));
	}
}

void upheap(int w){
int father;
	while (w > 1){
		father = w >> 1;
		if (d[h[w]] < d[h[father]]){
			swap(poz[h[w]], poz[h[father]]);
			swap(h[w], h[father]);
			w = father;	
		}
		else
			return;
	}
}

void downheap(int w){
int son;
	while (ls(w) <= k){
		son = ls(w);
		if (son+1 <= k)
			if (d[h[son]] > d[h[son+1]])
				++son;
		if (d[h[w]] > d[h[son]]){
			swap(poz[h[w]], poz[h[son]]);
			swap(h[w], h[son]);
			w = son;
		}
		else
			return;
	} 
}

void dijkstra(){
int i, min, nod2, cost2;
	for (i = 1; i <= n; ++i) poz[i] = -1, d[i] = INF;
	d[s] = 0; poz[s] = 1; h[1] = s; k = 1;

	while (k){
		min = h[1];
		swap(h[1], h[k]); 
		poz[h[1]] = 1;
		--k;
		downheap(1);
		
		for (i = 0; i < a[min].size(); ++i){
			nod2 = a[min][i].F; cost2 = a[min][i].S;
			if (d[min] + cost2 < d[nod2]){
				d[nod2] = d[min] + cost2;
				if (poz[nod2] == -1){
					++k;
					poz[nod2] = k;
					h[k] = nod2;
					upheap(k);
				}
				else
					upheap(poz[nod2]);
			}
		}
	}
}

void rezolva(){

	citire();
	dijkstra();
int i, ok = 1;
	for (i = 1; i <= n; ++i)
		if (d[i] != d2[i]){
			ok = 0; break;
		}
	if (ok) printf("DA\n");
	else	printf("NU\n");

}