#include <stdio.h>
#include <algorithm>
#define MAXM 150000
#define MAXN 50005

using namespace std;

struct wtf1
{
	int x,y,v;
};
struct wtf2
{
	int x,v;	
};
struct wtf3
{
	int x,y;
};

wtf1 a[MAXM];
wtf2 h[MAXN];
wtf3 p[MAXN];

int t[MAXN],r[MAXN],e[MAXN];
int n,m,k,S;
int R[MAXN];


bool cmp(wtf1 a, wtf1 b)
{
	if (a.x==b.x)
		return a.y<b.y;
	return a.x<b.x;	
}

void citire()
{
	char s[50]; int x,y,v,j,i;
	char s2[400000];
	
	scanf("%d%d%d",&n,&m,&S);
	gets(s);
	gets(s2);
	
	j=0;
	for (i=1; i<=n; i++)
	{
		x=0;
		while (s2[j]>='0' && s2[j]<='9')
		{
			x=x*10+s2[j]-'0';
			j++;			
		}
		j++; R[i]=x;
	}
	
	for (i=0; i<m; i++)
	{
		gets(s); x=0; y=0; v=0; j=0;
		
		while (s[j]>='0' && s[j]<='9')
		{
			x=x*10+s[j]-'0';
			j++;			
		}
		j++;
		while (s[j]>='0' && s[j]<='9')
		{
			y=y*10+s[j]-'0';
			j++;			
		}
		j++;
		while (s[j]>='0' && s[j]<='9')
		{
			v=v*10+s[j]-'0';
			j++;			
		}
		a[i].x=x; a[i].y=y; a[i].v=v;
	}
	
	sort(a,a+m,cmp);
	
	p[1].x=0;
	for (i=0,j=1; i<m;)
	{
		
		while (a[i].x==j && i<m)
			i++;
		p[j].y=i; j++;
		while (a[i].x!=j && j<n)
		{
			p[j].x=p[j].y=i;
			j++;			
		}
		p[j].x=i;
	}
	p[j].y=i;
}

void up(int i)
{
	if (i!=1)
		if (h[i].v<h[ i>>1 ].v)
		{
			wtf2 tmp1;
			t[h[i].x]=i>>1;	t[h[i>>1].x]=i;
			tmp1=h[i]; h[i]=h[ i>>1 ]; h[ i>>1 ]=tmp1;
			up(i>>1);
		}	
}

void down(int i)
{
	int m=i;
	if ((i<<1) <= k)
		if (h[m].v > h[(i<<1)].v)
			m=i<<1;
	if ((i<<1) +1 <= k)
		if (h[m].v > h[(i<<1) +1].v)
			m=(i<<1) +1;
		
	if (i!=m)
	{
		wtf2 tmp1;
		t[h[i].x]=m;	t[h[m].x]=i;
		tmp1=h[i]; h[i]=h[ m ]; h[ m ]=tmp1;
		down(m);
	}
}

void rezolv()
{
	int x,v,i,j;
	for (i=1; i<=n; i++)
	{
		x=h[1].x; v=h[1].v; r[x]=v; e[x]=1;
		t[h[k].x]=1; t[h[1].x]=0;
		h[1]=h[k]; h[k].x=0; h[k].v=0; k--;
		down(1);
		
		for (j=p[x].x; j<p[x].y; j++)
			if (!e[a[j].y])
				if (!t[ a[j].y ])
				{
					k++; t[a[j].y]=k;
					h[k].x=a[j].y; h[k].v=v+a[j].v;
					up(k);
				}		
				else
					if (v+(int)a[j].v  <  h[ t[ a[j].y ] ].v )
					{				
						h[ t[ a[j].y ] ].v=v+a[j].v;
						up(t[ a[j].y ]);
					}
	}
}

void afisare()
{
	int i;
	for (i=1; i<=n; i++)
		if (R[i]!=r[i])
		{
			printf("NU\n");
			return;
		}
	printf("DA\n");
}


int main()
{
	freopen("distante.in","r",stdin);
	freopen("distante.out","w",stdout);
	
	int i,Teste;
	scanf("%d",&Teste);
	
	for (i=0; i<Teste; i++)
	{
		citire();
		h[1].x=S; h[1].v=0; k=1;
		rezolv();
		r[S]=0;
		afisare();
		
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}