#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],Heap[maxN],Poz[maxN],Nod[maxN];

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

/*
	Heap[i] - costul de pe pozitia i in Heap
	Nod[i] - nodul de pe pozitia i in Heap
		Poz[i] - pozitia in Heap a nodului i
*/

void del(){
	
	Q=0;
	for(int i=1;i<=N;i++){
		S[i] = D[i] = Heap[i] = Poz[i] = Nod[i] = Sol[i] = 0;
		A[i].empty();
	}
	
}

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 Promoveaza(int N){
	
	while(Heap[N] < Heap[N/2] && N/2){
		
		Poz[Nod[N/2]] = N;
		Poz[Nod[N]] = N/2;
		std :: swap(Heap[N],Heap[N/2]);
		std :: swap(Nod[N],Nod[N/2]);
		N/=2;
		
	}
	
}

void Retrogradeaza(int N){
	
	while((Heap[N] > Heap[2*N] && Q>=2*N) || (Heap[N] > Heap[2*N+1] && Q>=2*N+1)){
		
		if(Heap[2*N] < Heap[2*N+1]){
			Poz[Nod[N]] = 2*N;
			Poz[Nod[2*N]] = N;
			std :: swap(Heap[N],Heap[N*2]);
			std :: swap(Nod[N],Nod[N*2]);
			N*=2;
		}
		else{
			Poz[Nod[N]] = 2*N+1;
			Poz[Nod[2*N+1]] = N;
			std :: swap(Heap[N],Heap[N*2+1]);
			std :: swap(Nod[N],Nod[N*2+1]);
			N = N*2 + 1;
		}
		
	}
	
}

void Adauga(int nod,int cost){
	
	Heap[++Q] = cost;
	Nod[Q] = nod;
	Poz[nod] = Q;
	
	Promoveaza(Q);
	Retrogradeaza(Q);
	
}

void Update(int nod,int cost){
	
	Heap[Poz[nod]] = cost;
	Promoveaza(Poz[nod]);
	Retrogradeaza(Poz[nod]);
	
}

void Delete(int N){
	
	Heap[N] = Heap[Q];
	Nod[N] = Heap[Q--];
	Poz[Nod[N]] = N;
	
	Promoveaza(N);
	Retrogradeaza(N);
	
}

void dijkstra(){
	
	for(int i=1;i<=N;i++){
		D[i] = inf;
		Adauga(i,D[i]);
	}
	
	for(it = A[Start].begin(),it2 = C[Start].begin(); it < A[Start].end(); it++,it2++){
		D[*it] = *it2;
		Update(*it,D[*it]);
	}
	
	S[Start]++;
	
	int min,poz;
	for(int i=1;i<N;i++){
		
		min = Heap[1];
		poz = Nod[1];
		
		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;
	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;
	
}