#include<iostream>
#include<fstream>
#include<vector>
const int maxx=50002,maxx1=maxx*1000,inf=maxx*1000;
using namespace std;
int n,m,start,t,i,min1[maxx],a,b,c,inc,sf,min2[maxx],coada[maxx1],j,val;
vector <pair<int , int> > x[maxx];
void read()
{
	scanf("%d %d %d\n",&n,&m,&start);
	for(i=1;i<=n;i++)
		scanf("%d",&min1[i]);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d\n",&a,&b,&c);
		x[a].push_back(make_pair(b,c));
		x[b].push_back(make_pair(a,c));
	}
}
int verif()
{
	for(i=1;i<=n;i++)
		if(min1[i]!=min2[i])
			return 0;
	return 1;
}
void solve()
{
	//bfs;
	inc=sf=1;
	coada[inc]=start;
	min2[start]=0;
	int nod;
	while(inc<=sf)
	{
		nod=coada[inc];
		for(i=0;i<x[nod].size();i++)
		{
			if(min2[nod]+x[nod][i].second<min2[x[nod][i].first])
			{
				sf++;
				coada[sf]=x[nod][i].first;
				min2[x[nod][i].first]=min2[nod]+x[nod][i].second;
				if(min2[x[nod][i].first]<min1[x[nod][i].first])
				{
					val=0;
					i=x[nod].size()+10;
					inc=sf+5;
				}
			}
		}
		inc++;
	}
	if(inc==sf+1)
		val=1;
	//bfs-end
	if(val==0)
		printf("NU\n");
	else
		if(verif()==0)
			printf("NU\n");
		else
			printf("DA\n");
}
void prepare()
{
	for(i=1;i<=n;i++)
		x[i].clear();
}
void prepare2()
{
	for(i=1;i<=n;i++)
		min2[i]=inf;
}
int main()
{
	freopen("distante.in","r",stdin);
	freopen("distante.out","w",stdout);
	scanf("%d",&t);
	for(j=1;j<=t;j++)
	{
		read();
		prepare2();
		solve();
		prepare();
	}
	return 0;
}