#include <fstream>
using namespace std;

const int N=50001,M=200002,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 bool comp(arc a,arc b)
{
	return a.x<b.x;
}

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 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;
	if (2*x<=v[0] && cmp(v[2*x],v[x]))
		m=2*x;
	if (2*x<v[0] && cmp(v[2*x+1],v[x]))
		m=2*x+1;
	if (m!=x)
	{
		sch(v[x],v[m]);
		down(m);
	}
}

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

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

void dijkstra(int x)
{
	int i,y,c;
	dist[x]=v[0]=0;
	add(x);
	while (v[0])
	{
		x=del();
		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;
				add(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;
		a[i+m].y=a[i].x;
		a[i+m].x=a[i].y;
		a[i+m].c=a[i].c;
	}
	m<<=1;
	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;
}