#include <stdio.h>
#include <string.h>

#define INF 99999999

typedef struct nodz {
	int nod;
	int c;
	nodz* next;
} *PNOD, NOD;

int n, m, nod1, nod2, cc, teste;
PNOD *list;
int *t, *d, *h, *poz, *df;
int source;
int nh, nod, bad;

void getmem();
void dijkstra();
void heap_build(int k);
void heap_up(int k);
void heap_down();
int heap_pop();
void swap(int i, int j);
void add_list(int u, int v, int c);

int main()
{
    int i, q;
	FILE *fin = fopen("distante.in", "r");
	FILE *fout = fopen("distante.out", "w");
	fscanf(fin, "%d", &teste);
	for (q = 1; q <= teste; ++q)
	{
		fscanf(fin, "%d%d%d", &n, &m, &source);
		getmem();
		for (i = 1; i <= n; ++i)
			fscanf(fin, "%d", &df[i]);
		for (i = 1; i <= m; ++i)
		{
			fscanf(fin, "%d%d%d", &nod1, &nod2, &cc);
			add_list(nod1, nod2, cc);
			add_list(nod2, nod1, cc);
		}

		dijkstra();
		bad = 0;
		for (i = 1; i <= n; ++i)
			if (d[i] != df[i])
			{
				bad = 1;
				break;
			}
		if (!bad)
			fprintf(fout, "DA\n");
		else
			fprintf(fout, "NU\n");
	}
	fclose(fin);
	fclose(fout);

	return 0;
}

void getmem()
{
	list = new PNOD [n+4];
	t = new int [n+4];
	d = new int [n+4];
	h = new int [n+4];
	poz = new int [n+4];
	df = new int [n+4];
	for (int i = 0; i <= n; ++i)
	{
		list[i] = 0;
		t[i] = 0;
		d[0] = 0;
		poz[0] = 0;
	}
}

void add_list(int u, int v, int c)
{
	PNOD p = new NOD;
	p->nod = v;
	p->c = c;
	p->next = list[u];
	list[u] = p;
}

void dijkstra()
{
     int i;
	for (i = 0; i <= n; ++i)
	{
		d[source] = INF;
		t[i] = 0;
	}
	for (i = 0; i < n; ++i) // introducem in heap toate nodurile
	{
		h[i] = i + 1;
		poz[i+1] = i;
	}

	d[source] = 0;
	heap_build(n);
	nh = n;
	while (nh > 0)
	{
		nod = heap_pop();
		for (PNOD p = list[nod]; p; p = p ->next)
			if (d[p->nod] > d[nod] + p->c)
			{
				d[p->nod] = d[nod] + p->c;
				t[p->nod] = nod;
				heap_up(poz[p->nod]);
			}
	}
}

void heap_build(int k)
{
	for (int i = 1; i < k; ++i)
		heap_up(i);
}

void heap_up(int k)
{
	if (k <= 0) return;
	int aux = (k-1) / 2;
	if (d[ h[k] ] < d[ h[aux] ])
	{
		swap(k, aux);
		heap_up(aux);
	}
}

void swap(int i, int j)
{
	int aux;
	aux = h[i];
	h[i] = h[j];
	h[j] = aux;
	poz[h[i]] = i;
	poz[h[j]] = j;
}

void heap_down(int r, int k)
{
	int st, dr, i;
	if (2*r+1 <= k)
	{
		st = h[2*r+1];
		if (2*r+2 <= k)
			dr = h[2*r+2];
		else
			dr = st-1;
		if (st > dr)
			i = 2*r+1;
		else
			i = 2*r+2;
		if (d[ h[r] ] > d[ h[i] ])
		{
			swap(r, i);
			heap_down(i, k);
		}
	}
}

int heap_pop()
{
	swap(0, nh-1);
	poz[ h[nh-1] ] = 0;
	nh--;

	heap_down(0, nh-1);
	return h[nh];
}