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

#define inf INT_MAX/2
#define maxN 50005

int T,Q;
int N,M,Start,Sol[maxN];
int D[maxN],S[maxN],H[maxN],P[maxN],X[maxN];

std :: vector <int> A[maxN],C[maxN];
std :: vector <int> :: iterator it,it2;

/*
	H[i] - costul de pe Xitia i in H
	P[i] - Pul de pe Xitia i in H
		X[i] - Xitia in H a Pului i
*/

void del(){
	
	Q=0;
	for(int i=1;i<=N;i++){
		S[i] = D[i] = H[i] = X[i] = P[i] = Sol[i] = 0;
		A[i].clear();
		C[i].clear();
	}
	
}

void read(){
	
	scanf("%d%d%d",&N,&M,&Start);
	
	for(int i=1;i<=N;i++)
		scanf("%d",&Sol[i]);
	
	int x,y,c;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&x,&y,&c);
		A[x].push_back(y);
		C[x].push_back(c);
	}
	
}

void Avansare(int n){
	
	while(H[n] < H[n/2] && n/2){
		
		X[P[n]] = n/2;
		X[P[n/2]] = n;
		std :: swap(H[n],H[n/2]);
		std :: swap(P[n],P[n/2]);
		n/=2;
		
	}
	
}

void Retrogradare(int n){
	
	while((H[n] > H[n*2] && Q>n*2) || (H[n] > H[n*2+1] && Q>n*2+1)){
		if(H[n*2] < H[n*2+1]){
			
			X[P[n]] = n*2;
			X[P[n*2]] = n;
			std :: swap(H[n],H[n*2]);
			std :: swap(P[n],P[n*2]);
			n*=2;
			
		}
		else{
			
			X[P[n]] = n*2+1;
			X[P[n*2+1]] = n;
			std :: swap(H[n],H[n*2+1]);
			std :: swap(P[n],P[n*2+1]);
			n = n*2 + 1;
			
		}
	}
	
}

void Adaugare(int nod,int cost){
	
	H[++Q] = cost;
	P[Q] = nod;
	X[nod] = Q;
	
	Avansare(Q);
	Retrogradare(Q);
	
}

void Update(int nod,int cost){
	
	H[X[nod]] = cost;
	Avansare(X[nod]);
	Retrogradare(X[nod]);
	
}

void Delete(int n){
	
	H[1] = H[Q];
	P[1] = P[Q--];
	Avansare(n);
	Retrogradare(n);
	
}

void dijkstra(){
	
	for(int i=1;i<=N;i++){
		D[i] = inf;
		Adaugare(i,D[i]);
	}
	
	int poz = Start;
	S[poz]++;
	
	for(it = A[poz].begin(), it2 = C[poz].begin(); it < A[poz].end(); it++,it2++){
		
		D[*it] = *it2;
		Update(*it,D[*it]);
		
	}
	
	int min;
	for(int i=1; i<N; i++){
		
		min = H[1];
		poz = P[1];
		S[poz]++;
		
		for(it = A[poz].begin(), it2 = C[poz].begin(); it < A[poz].end(); it++,it2++){
			
			if(min + *it2 < D[*it]){
				D[*it] = min + *it2;
				Update(*it,D[*it]);
			}
			
		}
		
		Delete(1);
		
	}
	
}

void solve(){
	
	int i;
	D[Start] = 0;
	for(i=1;i<=N;i++){
		if(D[i]>=inf) D[i] = 0;
		if(D[i]!=Sol[i]){
			printf("NU\n");
			break;
		}
	}
	if(i>N) printf("DA\n");
	
}

int main(){
	
	freopen("distante.in","r",stdin);
	freopen("distante.out","w",stdout);
	
	scanf("%d",&T);
	
	for(int i=1;i<=T;i++){
		
		read();
		dijkstra();
		solve();
		del();
		
	}
	
	return 0;
	
}