#include <stdio.h>
#define NMAX 50032
#define INF "distante.in"
#define OUF "distante.out"
int cost[NMAX],t,n,m,source;
struct nod
{
	int x,cost;
	nod *next;
};
struct lst
{
	nod *p,*q;
	void init()
	{
		p=q=NULL;
	}
	void insert(int nd,int val)
	{
		nod *op;
		op=new nod;
		op->x=nd;op->cost=val;
		if(p==NULL) p=q=op;
		else
		{
			q->next=op;
			q=op;
		}
	}
}list[NMAX];
void delete_list(nod *op)
{
	if(op!=NULL)
	{
		delete_list(op->next);
		delete op;
	}
}
int main()
{
	int k,i,j,a,b,c,ok,min,val;
	FILE *in,*out;
	nod *op;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%d",&t);
	for(k=1;k<=t;k++)
	{
		ok=1;
		fscanf(in,"%d %d %d",&n,&m,&source);
		for(i=1;i<=n;i++)
		{
			fscanf(in,"%d",cost+i);
			list[i].init();
		}
		if(cost[source]!=0) ok=0;
		else
		{
			for(i=1;i<=m;i++)
			{
				fscanf(in,"%d %d %d",&a,&b,&c);
				list[a].insert(b,c);
				list[b].insert(a,c);
			}
			for(i=1;i<=n&&ok;i++)
			{
				min=(1<<30);
				op=list[i].p;
				while(op!=NULL)
				{
					val=cost[op->x]+op->cost;
					if((val)<min) min=val;
					op=op->next;
				}
				if(i!=source&&cost[i]!=min) ok=0;
			}
			delete_list(list[i].p);
		}
	        if(ok) fprintf(out,"DA\n");
			else fprintf(out,"NU\n");
	}
	fclose(in);fclose(out);
	return 0;
}