#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
#define MAX 50005
#define INF 1<<30
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;

struct compar{
	bool operator() (pii a, pii b) {return  a.sec > b.sec;}
};

int t, n, m, s, i, j, x, y, z, d[MAX], dr[MAX];
vector<pii> l[MAX];
priority_queue<pii, vector<pii>, compar> q;
bool viz[MAX];

void dijkstra(int s);

int main(){
	freopen("distante.in", "r", stdin);
	freopen("distante.out", "w", stdout);
	scanf("%d", &t);
	for(i = 0; i < t; i++){
		memset(viz, 0, sizeof(viz));
		scanf("%d%d%d", &n, &m, &s);
		for(j = 1; j <= n; j++){
			scanf("%d", &d[j]);
			l[j].clear();
		}
		for(j = 0; j < m; j++){
			scanf("%d%d%d", &x, &y, &z);
			l[x].push_back(make_pair(y, z));
		}
		dijkstra(s);
		for(j = 1; j <= n; j++)
			if(d[j] != (dr[j] == INF ? 0 : dr[j])){
				printf("NU\n");
				break;
			}
		if(j > n)
			printf("DA\n");
	}
	return 0;
}

void dijkstra(int s){
	for(int i = 1; i <= n; i++)
		dr[i] = INF;
	dr[s] = 0;
	pii aux;
	aux.fir = s;
	aux.sec = d[s];
	q.push(aux);

	while(!q.empty()){
		int x = q.top().fir;
		q.pop();

		if(viz[x])
			continue;
		viz[x] = 1;
		while(!l[x].empty()){
			aux = l[x].back();
			l[x].pop_back();
			if(dr[x] + aux.sec < dr[aux.fir]){
				dr[aux.fir] = dr[x] + aux.sec;
				aux.sec = dr[aux.fir];
				q.push(aux);
			}
		}
	}
}