#include <fstream>

using namespace std;

#define INF 1000000000

#define N 50001
#define M 100000

int h[N]; //heap
int poz[N];
int d[N]; //distanta de la nodul 1 la celelalte noduri
int lh; //dimensiune (lungime) heap
int n, m, s; 

struct arc
{
	int x,y,c;
};

arc w[M];
int nrv[N];
int *la[N], *lc[N];

void elib_res()
{
	int i;
	for(i = 1; i <= n; ++i)
	{
		delete la[i];
		delete lc[i];
	}
}

void citeste_test(ifstream& fi) //citeste din fisier
{
	int x,y,c;
	fi >> n >> m >> s;
	int i;
	for(i = 1; i <= n; ++i) fi >> d[i];
	for(i=1;i<=m;++i)
	{
		fi >> x >> y >> c;
		w[i].x=x;
		nrv[x]++;
		w[i].y=y;
		w[i].c=c;
	}
	for(i=1;i<=n;++i) 
	{
		la[i]=new int[nrv[i] + 1];
		lc[i]=new int[nrv[i] + 1];
		la[i][0] = lc[i][0] = 0;
	}
	for(i=1;i<=m;++i)
	{
		la[w[i].x][++la[w[i].x][0]] = w[i].y;
		lc[w[i].x][++lc[w[i].x][0]] = w[i].c;
	}
}
bool check_dijkstra()
{
	int i, e, gasit;

	//verific sursa
	if(d[s] != 0) return false;

	for(e = 1; i <= n; ++e)
	{
		if(e == s) continue;
		gasit = 0;
		for(i = 1; i <= nrv[e]; ++i)
		{
			if(d[e] == d[la[e][i]] + lc[e][i]) gasit = 1;
			if(d[e] > d[la[e][i]] + lc[e][i]) return false;
		}
		if(!gasit) return false;
	}
	return true;
}

int main()
{
	ifstream fi("distante.in");
	ofstream fo("distante.out");
	int t;
	fi >> t;
	while(t--)
	{
		citeste_test(fi);
		fo << (check_dijkstra() ? "DA" : "NU") << "\n";
		elib_res();
	}
	return 0;
}