#include<fstream>
#define inf 1000000
using namespace std;
int n,m,i,j,nrt,start,q[100001],c,x,y,*g1[50001],*g2[50001],d[50001],a[50001];
int st,dr,p;
int main()
{
	ifstream f("distante.in");
	ofstream g("distante.out");
	f>>nrt;
	while(nrt--)
	{
		f>>n>>m>>start;
		for(i=1;i<=n;i++)
		{
			f>>a[i];
			d[i]=inf;
			g1[i]=(int*)realloc(g1[i],sizeof(int));
			g1[i][0]=0;
			g2[i]=(int *)realloc(g2[i],sizeof(int));
			g2[i][0]=0;
		}
		for(i=1;i<=m;i++)
		{
			f>>x>>y>>c;
			g1[x][0]++;
			g1[x]=(int*)realloc(g1[x],(g1[x][0]+1)*sizeof(int));
			g1[x][g1[x][0]]=y;
			g1[y][0]++;
			g1[y]=(int *)realloc(g1[y],(g1[y][0]+1)*sizeof(int));
			g1[y][g1[y][0]]=x;
			g2[x][0]++;
			g2[x]=(int *)realloc(g2[x],(g2[x][0]+1)*sizeof(int));
			g2[x][g2[x][0]]=c;
			g2[y][0]++;
			g2[y]=(int *)realloc(g2[y],(g2[y][0]+1)*sizeof(int));
			g2[y][g2[y][0]]=c;
		}
		d[start]=0;
		q[1]=start;
		st=dr=1;
		while(st<=dr)
		{
			p=q[st++];
			for(i=1;i<=g1[p][0];i++)
				if(d[g1[p][i]]>d[p]+g2[p][i])
				{
					d[g1[p][i]]=d[p]+g2[p][i];
					q[++dr]=g1[p][i];
				}
		}
	
		int ok=1;
		i=0;
		while(ok&&i<n)
		{
			++i;
			if(a[i]!=d[i])
				ok=0;
		}
		if(ok)
			g<<"DA\n";
		else
			g<<"NU\n";
	}
	return 0;
}