#include <fstream>
using namespace std;

const int N=50001,M=100002,inf=1<<30;
const char rasp[][6]={"NU\n","DA\n"};
struct arc{int x,y,c;} a[M];
int v[M],s[N],dist[N],q[N],n,m;

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

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

inline bool cmp(int a,int b)
{
	return dist[a]<dist[b];
}

inline bool comp(arc a,arc b)
{
	return a.x<b.x;
}

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

inline void down(int x)
{
	int m=x,st=2*x,dr=2*x+1;
	if (st<=x && cmp(v[st],v[x]))
		m=st;
	if (dr<=x && cmp(v[dr],v[x]))
		m=dr;
	if (m!=x)
	{
		sch(v[m],v[x]);
		down(m);
	}
}

inline void push(int x)
{
	v[++v[0]]=x;
	up(v[0]);
}

inline int pop()
{
	int x=v[1];v[1]=v[v[0]--];
	down(1);
	return x;
}

void dijkstra(int x)
{
	int i,y,c;
	dist[x]=0;
	push(x);
	while (v[x])
	{
		x=pop();
		for (i=s[x];i<s[x+1];i++)
		{
			y=a[i].y;c=a[i].c;
			if (dist[y]>dist[x]+c)
			{
				dist[y]=dist[x]+c;
				push(y);
			}
		}
	}
}

int exe()
{
	int x,i,j;
	in>>n>>m>>x;
	for (i=1;i<=n;i++)
	{
		in>>q[i];
		dist[i]=inf;
	}
	for (i=1;i<=m;i++)
		in>>a[i].x>>a[i].y>>a[i].c;
	sort(a+1,a+m+1,comp);
	for (i=j=1,s[n+1]=m+1;i<=n;s[i]=j,i++)
		for (;a[j].x<i && j<=m;j++);
	dijkstra(x);
	for (i=1;i<=n;i++)
		if (q[i]!=dist[i])
			return false;
	return true;
}

int main()
{
	int t;
	in>>t;
	while (t--)
		out<<rasp[exe()];
	return 0;
}