using namespace std;
#include <cstdio>
#include <vector>
#include <string>
#define left(i) ((i)<<1)
#define right(i)  (((i) << 1)|1)
#define tata(i) ((i)>>1)
#define maxn 50001
int d1[maxn],d[maxn], n, m, s;
int H[maxn], poz[maxn], nh;
struct nod { int x, c; nod(){}; nod(int a, int b){x=a; c=b;};}__attribute__ ((packed));

vector<vector<nod> > a;
void solve();
void citire()
{
	freopen("distante.in", "r",stdin);
	int T, i, p, q, c;
	scanf("%d\n", &T);
	while(T--)
	{
		a.clear();
		scanf("%d %d %d\n", &n, &m, &s);
		a.resize(n+1);
		for(i=1;i<=n;++i) scanf("%d ", d1+i);
		while(m--)
		{
			scanf("%d %d %d\n", &p, &q, &c);
			a[p].push_back(nod(q,c)); 
		}
		solve();
		int ok=1;
		for(i=1;i<=n;++i) if(d1[i]!=d[i]) { ok=0; break;}
		if(ok) printf("DA\n");
			else printf("NU\n");
	}
}
inline void swap(int i, int j)
{
	int t=H[i];
	H[i]=H[j];
	H[j]=t;
	poz[H[i]]=i;
	poz[H[j]]=j;
}
void heapup(int i)
{
	if(i==1) return;
	if(d[H[i]]<d[H[tata(i)]]) swap(i, tata(i)), heapup(tata(i));
}

void heapdown(int i)
{
	int min=i;
	if(left(i)<=nh && d[H[i]]>d[H[left(i)]]) min=left(i);
	if(right(i)<=nh && d[H[min]]>d[H[right(i)]])min=right(i);
	if(i!=min)swap(i,min), heapdown(min);
}


void insert_heap(int val)
{
	H[++nh]=val;
	heapup(nh);
}

void pop_heap()
{
	swap(1, nh--);
	heapdown(1);
}


void solve()
{
	vector<nod>::iterator it;
	memset(d, 0x3f3f3f3f, sizeof(d));
	memset(H, 0 ,sizeof(H));
	d[s]=0;
	int i;
	//for(i=1;i<=n;++i) H[i]=i, poz[i]=i;
	//for(i=n>>1;i>=1;--i) heapdown(i);
	//nh=n;
	nh=0;
	for(i=1;i<=n;++i) insert_heap(i);
	int u;
	
	while(nh)
	{
		u=H[1];
		pop_heap();
		
		for(it=a[u].begin();it!=a[u].end();++it)
			if(d[u]+it->c < d[it->x])
			{
				d[it->x]=d[u]+it->c;
				heapup(poz[it->x]);
			}
	}
}
	
	
	
int main()
{
	freopen("distante.out", "w",stdout);
	citire();
	return 0;
}