#include<cstdio>
#include<vector>
using namespace std;
const int lim=2000000000;

int n,m,s,x,y,c,d[50001],h[50001],poz[50001],ok[50001],t,i,aux;
vector<pair<int,int> > v[50001];

inline void sp(int i,int j)
{
	aux=h[i];h[i]=h[j];h[j]=aux;
	poz[h[i]]=i;poz[h[j]]=j;
}

void up(int i)
{
	if(i<=1) return;
	int t=i>>1;
	if(d[h[t]]>d[h[i]]){
		sp(i,t);
		up(t);}
}

void dw(int i)
{
	int t=i<<1;
	if(t<=m){
		if(t<m && d[h[t]] > d[h[t+1]]) t++;
		if(d[h[t]]<d[h[i]]){
			sp(i,t);
			dw(t);}	}
}
	
int sc()
{
	if(m==1) return 0;
	sp(1,m);
	m--;
	dw(1);
	return h[m+1];
}
inline void check()
{
	d[s]=0;
	m=n;
	sp(1,s);
	for(;;){
		y=sc();
		if(!y) break;
		for(i=0;i<v[y].size();++i)
			if(d[v[y][i].first] > d[y]+v[y][i].second){
				d[v[y][i].first]=d[y]+v[y][i].second;
				up(v[y][i].first);}}
	for(i=1;i<=n;i++)
		if(d[i]!=ok[i]) {printf("NU\n");return;}
	printf("DA\n");
}
int main()
{
	freopen("distante.in","r",stdin);
	freopen("distante.out","w",stdout);
	scanf("%d",&t);
	for(;t;t--){
	scanf("%d %d %d",&n,&m,&s);
	for(i=1;i<=n;i++){
		scanf("%d",&ok[i]);
		d[i]=lim;
		poz[i]=i;
		h[i]=i;
		v[i].clear();}
	for(i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&c);
		v[x].push_back(make_pair(y,c));
		v[y].push_back(make_pair(x,c));}
	check();}
	fclose(stdout);
	return 0;
}