#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

#define Nmax 50001
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define L(x) ( (x)<<1 )
#define R(x) ( ( (x)<<1 ) + 1 )

FILE *f=fopen ("distante.in","r");
FILE *g=fopen ("distante.out","w");

int Heap[Nmax], poz[Nmax], cost[Nmax], ini[Nmax], N, M, Lgheap;
vector < pair < int, int > > G[Nmax];

void Swap (int x, int y){
	swap (Heap[x],Heap[y]);
	swap (poz[Heap[x]],poz[Heap[y]]);
}

void Initialize (int start){
	
	for (int i = 1 ; i <= N ; ++i){
		Heap[i] = i;
		poz[i] = i;
		cost[i] = inf;
		G[i].clear();
	}
	cost[0] = -1;
	cost[start] = 0;
	Swap (1, start);
	Lgheap = N;
}

void UpHeap (int nod){
	
	if ( cost[ Heap[nod>>1] ] < cost[ Heap[nod] ] ) return; 
	
	Swap ( nod, nod >>1 );
	UpHeap ( nod >>1 );
}

void DownHeap (int nod){
	int st, dr;
	
	if ( L(nod) > Lgheap ) return;
	
	st = cost[ Heap[L(nod)] ];
	
	if ( R(nod) > Lgheap ) dr = st + 1;
	else dr = cost[ Heap[R(nod)] ];
	
	if (st <= dr){
		if (st < cost[ Heap[nod] ]){
			Swap ( nod, L(nod) );
			DownHeap ( L(nod) );
		}
	}
	else{
		if (dr < cost[ Heap[nod] ]){
			Swap ( nod, R(nod) );
			DownHeap ( R(nod) );
		}
	}
}

void Dijkstra (int start){
	int actual;
	vector < pair < int, int > > :: iterator it;
	
	while (Lgheap){
		actual = Heap[1];
		Swap ( 1, Lgheap-- );
		DownHeap (1);
		
		for (it = G[actual].begin(); it < G[actual].end(); ++it){
			if (cost[it -> first] > cost[actual] + it -> second){
				cost[it -> first] = cost[actual] + it -> second;
				UpHeap (poz[it -> first]);
			}
		}
	}
}

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

int main(){
	int T, start, x, y, c;
	
	fscanf (f,"%d",&T);
	
	while (T--){
		fscanf (f,"%d%d%d",&N,&M,&start);
		
		Initialize (start);
		
		for (int i = 1; i <= N; ++i)
			fscanf (f,"%d",&ini[i]);
		
		for (int i = 1; i <= M ; ++i){
			fscanf (f,"%d%d%d",&x,&y,&c);
			G[x].pb ( mp (y,c) );
			G[y].pb ( mp (x,c) );
		}
		
		Dijkstra (start);
		
		check() ? fprintf(g,"DA\n") : fprintf (g,"NU\n");
	}
	
	return 0;
}