#include<fstream>
#define Max 20000
#define Infinit 100001

using namespace std;

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

int n,root,a[Max][Max],m,d[Max],s[Max],t[Max],nrt;
void clean()
{
	int i,j;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++)
			if(i == j)
				a[i][j] = 0;
			else
				a[i][j] = Infinit;
}
void read()
{
	int i,x,y,c;
	fin>>n>>m>>root;
	clean();
	for(i = 1; i <= n; i++)
		fin>>t[i];
	for(i = 1; i <= m; i++)
	{
		fin>>x>>y>>c;
		a[x][y] = c;
		a[y][x] = c;
	}

}	
int verif()
{
	int i;
	for(i = 1; i <= n; i++)
		if(d[i] != t[i])
		{
			fout<<"NU";
			return 0;
		}
fout<<"DA";
fout<<"\n";
return 1;
}
void dijkstra()
{
	int i,j,poz,min;
	s[root] = 1;
	poz = root;
	for(i = 1; i <= n; i++)
		d[i] = a[root][i];
	d[root] = 0;
	for(i = 1; i <= n-1; i++)
	{
		min = Infinit;
		for(j = 1; j <= n; j++)
			if(s[j] == 0)
				if(d[j] < min)
				{
					min = d[j];
					poz = j;
				}
				s[poz] = 1;
		for(j = 1; j <= n; j++)
			if(s[j] == 0)
				if(d[j] > d[poz]+a[poz][j])
					d[j] = d[poz]+a[poz][j];
	}
	verif();
}
int main()
{
	int i;
	fin>>nrt;
	for(i = 1; i <= nrt; i++)
	{
		read();
	//	fout<<"\n";
		//for(k = 1; k <= n; k++)
		//{
		//	for(j = 1;j <= n; j++)
		//		fout<<a[k][j]<<" ";
		//		fout<<"\n";
		//}
		dijkstra();
	}
	
fin.close();
fout.close();

return 0;

}