#include <fstream>
using namespace std;

const char r[][5]={"NU\n","DA\n"};
struct coarda{int x,y,d;} a[1<<18];
int v[1<<17],dist[1<<17],sol[1<<17],st[1<<17],poz[1<<17],m,n;

ifstream in("distante.in");
ofstream out("distante.out");

inline void sch(int &a,int &b)
{
	int d=a;a=b;b=d;
}

bool cmp(coarda a,coarda b)
{
	return a.x<b.x || a.x==b.x && a.y<b.y;
}

bool verif()
{
	for (int i=1;i<=n;i++)
		if (dist[i]!=sol[i])
			return false;
	return true;
}

inline void up(int x)
{
	if (x>1 && dist[v[x]]>dist[v[x>>1]])
	{
		up(x>>1);
		sch(v[x],v[x>>1]);
	}
}

inline void down(int x)
{
	int m=x;
	if (2*x<=v[0] && dist[v[x]]>dist[v[x<<1]])
		m=x<<1;
	if (2*x<v[0] && dist[v[x]]>dist[v[2*x+1]])
		m=2*x+1;
	if (m!=x)
	{
		sch(m,x);
		sch(v[m],v[x]);
		sch(poz[v[m]],poz[v[x]]);
		down(m);
	}
}

void init()
{
	for (int i=0;i<1<<16;i++)
	{
		dist[i]=1<<30;
		poz[i]=0;
	}
}	

void set_st()
{
	int i,j;
	for (i=j=1;i<=n;i++)
	{
		for (;a[j].x<i && j<=m;j++);
		st[i]=j;
	}
	st[n+1]=m+1;
}

inline void add(int x,int y,int d)
{
	if (dist[y]>dist[x]+d)
	{
		dist[y]=dist[x]+d;
		if (poz[y])
			down(poz[y]);
		else
		{
			poz[y]=++v[0];
			v[v[0]]=y;
			up(y);
		}
	}
}

int main()
{
	int s,t,i;
	in>>t;
	while (t--)
	{
		init();
		in>>n>>m>>s;
		for (i=1;i<=n;i++)
			in>>sol[i];
		for (i=1;i<=m;i++)
		{
			in>>a[i].x>>a[i].y>>a[i].d;
			a[i+m].x=a[i].y;
			a[i+m].y=a[i].x;
			a[i+m].d=a[i].d;
		}
		m<<=1;
		sort(a+1,a+m+1,cmp);
		set_st();
		dist[s]=0;
		v[0]=1;
		v[1]=s;
		poz[s]=1;
		while (v[0])
		{
			s=v[1];
			for (i=st[s];i<st[s+1];i++)
				add(s,a[i].y,a[i].d);
			v[1]=v[v[0]--];
			down(1);
		}
		out<<r[verif()];
	}
	return 0;
}