#include <fstream>
#include <vector>
using namespace std;

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

const int dim = 50005, OO = (1 << 31) - 1;
int T, N, M, S;
int H[dim], D[dim], P[dim], DB[dim], viz[dim];
struct vec { int v, c; };
vector <vec> V[dim];

int cnt (int n1, int n2)
{
	return D[H[n1]] < D[H[n2]];
}

void upheap (int f)
{
	int t = f >> 1;
	while (t != 0 && cnt (f, t))
	{
		swap (H[t], H[f]);
		swap (P[H[t]], P[H[f]]);
		
		f = t;
		t = f >> 1;
	}	
}

void downheap (int t)
{
	int f = t << 1;
	if (f+1 <= H[0] && cnt (f+1, f)) f++;
	while (f <= H[0] && cnt (f, t))
	{
		swap (H[t], H[f]);
		swap (P[H[t]], P[H[f]]);
		
		t = f;
		f = t << 1;
		if (f+1 <= H[0] && cnt (f+1, f)) f++;
	}
}

void cit ()
{
	vec v;	
	fi >> N >> M >> S;
	for (int i = 0; i <= N; i++)
	{
		D[i] = OO;
		H[i] = P[i] = viz[i] = 0;
		while ( !V[i].empty() )
			V[i].pop_back ();
	}
	for (int i = 1; i <= N; i++)
		fi >> DB[i];
	for (int i = 1, a, b; i <= M; i++)
	{
		fi >> a >> b >> v.c;
		v.v = a;
		V[b].push_back (v);
		v.v = b;
		V[a].push_back (v);
	}
	
	D[S] = 0;
	viz[S] = 1;
	for (int i = 0, v, c; i < V[S].size(); i++)
	{
		v = V[S][i].v;
		c = V[S][i].c;
		D[v] = c;
	}
	for (int i = 1; i <= N; i++)
	{
		if (i == S) continue;
		H[++H[0]] = i;
		P[i] = H[0];
		upheap (H[0]);
	}
}

void dijkstra ()
{
	for (int i = 2, j, n, v, c; i <= N; i++)
	{
		n = H[1];
		viz[n] = 1;
		
		H[1] = H[H[0]];
		P[H[H[0]]] = 1;
		H[0]--;
		downheap (1);
		
		for (j = 0; j < V[n].size(); j++)
		{
			v = V[n][j].v;
			c = V[n][j].c;
			if (viz[v] == 1) continue;
			
			if (D[v] > D[n] + c)
			{
				D[v] = D[n] + c;
				upheap (P[v]);
				downheap (P[v]);
			}
		}		
	}
}

void afi ()
{
	int ok = 1;
	for (int i = 1; i <= N; i++)
		if (D[i] != DB[i])
			{ ok = 0; break; }
	if (ok)
		fo << "DA\n";
	else
		fo << "NU\n";
}

int main ()
{
	fi >> T;
	while (T--)
	{
		cit ();
		dijkstra ();
		afi ();
	}
	
	return 0;
}