#include<stdio.h>
#include<string.h>
#define N 50001
#define M 100001
int t,n,m,s,dist[N],ok=1;
const int INF=1<<30;
int d[N],use[N],niv[N],c[N+1];
struct vec{
	int x,y,c;
}v[M];
struct col{
	int x,c;
}*a[N];
void solve(void);
void read_01();
void rez();
void read()
{
	int i1,i;
	scanf("%d",&t);
	for(i1=1;i1<=t;i1++)
	{
		scanf("%d%d%d",&n,&m,&s);
		for(i=1;i<=n;i++)
			scanf("%d",&dist[i]);
		/*for(i=1;i<=m;i++)
			scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].c);*/
		memset(use,0,sizeof(use));
		memset(niv,0,sizeof(niv));
		memset(d,0,sizeof(d));
		//memset(dist,0,sizeof(dist));
		memset(c,0,sizeof(c));
		read_01();
		rez();
		ok=1;
		solve();
		ok==1?printf("DA\n"):printf("NU\n");
		for(i=1;i<=n;i++)
			delete a[i];
	}
}
void solve()
{
	/*int i,c=1;
	for(i=1;i<=n;i++)
		if(dist[i]==0&&s!=i)
			ok=0;
	for(i=1;i<=n;i++)
		if(dist[v[i].a]+v[i].c<dist[v[i].b])
			ok=0;	
	c=1;
	for(i=1;i<=n;i++)
		if(dist[v[i].a]+v[i].c==dist[v[i].b])
			c=0;
	c=1;
	for(i=1;i<=n;i++)
		if(dist[v[i].b]+v[i].c==dist[v[i].a])
			c=0;
	if(c)
		ok=0;*/
	for(int i=1;i<=n;i++)
		if(dist[i]!=d[i])
			ok=0;
}
void read_01()
{
	int i;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
		niv[v[i].x]++;
		niv[v[i].y]++;
	}
	for(i=1;i<=n;i++)
	{
		a[i]=new col[niv[i]+1];
		a[i][0].x=a[i][0].c=0;
	}
	for(i=1;i<=m;i++)
	{
		a[v[i].x][++a[v[i].x][0].x].x=v[i].y;
		a[v[i].y][++a[v[i].y][0].x].x=v[i].x;
		a[v[i].x][++a[v[i].x][0].c].c=v[i].c;
		a[v[i].y][++a[v[i].y][0].c].c=v[i].c;
	}
	/*for(i=1;i<=n;i++)
		for(int j=1;j<=a[i][0].x;j++)
			printf("%d %d %d\n",i,a[i][j].x,a[i][j].c);*/
	for(i=1;i<=n;i++)
		d[i]=INF;
	/*for(i=1;i<=a[1][0].x;i++)
		d[a[1][i].x]=a[1][i].c;*/
	d[s]=0;
}
void rez()
{
	int i,ic,sf,nod;
	c[1]=s;
	use[s]=1;
	for(ic=sf=1;ic-sf!=1;ic=(ic<N?ic+1:0))
	{
		nod=c[ic];
		for(i=1;i<=a[nod][0].x;i++)
			if(d[a[nod][i].x]>d[nod]+a[nod][i].c)
			{
				d[a[nod][i].x]=d[nod]+a[nod][i].c;
				if(!use[a[nod][i].x])
				{
					sf=(sf<N?sf+1:0);
					c[sf]=a[nod][i].x;
					use[a[nod][i].x]=1;
				}
			}
		use[nod]=0;
	}
	/*for(i=2;i<n;i++)
		printf("%d ",d[i]==INF?0:d[i]);
	printf("%d\n",d[n]==INF?0:d[i]);*/
}
int main()
{
	freopen("distante.in","r",stdin);
	freopen("distante.out","w",stdout);
	read();
	return 0;
}