#include <stdio.h>

#define INF 99999999
#define MAX 50006

typedef struct node {
	int val, cost;
	node *next;
} *PNOD, NOD;

int n, m, source, u, v, c, teste, nod1, nod2, cc, bad;
int hsize;
int *d, *df, *h, *poz, *caract;
PNOD *list;

void add_list(int x, int y, int cc);
void dijkstra();
void buildHeap();
int extractMin();
void moveUp(int nod);
void rebuildHeap(int nod);
void getmem();
void clearz();

int main()
{
	int i, q;
	FILE *fin = fopen("distante.in", "r");
	FILE *fout = fopen("distante.out", "w");
	getmem();
	fscanf(fin, "%d", &teste);
	for (q = 1; q <= teste; ++q)
	{
		fscanf(fin, "%d%d%d", &n, &m, &source);
		clearz();
		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");
		else
			fprintf(fout, "NU");
		if (q < teste)
		    fprintf(fout, "\n");
	}
	fclose(fin);
	fclose(fout);
    
    return 0;
}

void getmem()
{
	d = df = h = poz = caract = 0;
	list = 0;
	while (!list) list = new PNOD [MAX+4];
	while (!d) d = new int [MAX+4];
	while (!df) df = new int [MAX+4];
	while (!h) h = new int [MAX+4];;
	while (!poz) poz = new int [MAX+4];
	while (!caract) caract = new int [MAX+4];
}

void clearz()
{
	for (int i = 0; i <= n+2; ++i)
	{
        list[i] = 0;
        caract[i] = 0;
	}
}

void dijkstra()
{
    int curr;     // tine nodul cu costul cel mai mic
    buildHeap();  // construim heapul
    
    while (hsize) // cat timp heapul nu e gol
    {
        curr = extractMin();   // luam cel mai mic
		caract[curr] = 0;  // si il extragem din heap
        for (PNOD x = list[curr]; x; x = x->next) // parcurgem vecinii nodului
            if (d[x->val] > d[curr] + x->cost)     // daca putem relaxa o muchie
            {
                d[x->val] = d[curr] + x->cost;     // o relaxam
                if (caract[x->val])                // si o urcam daca e in heap
                    moveUp(x->val);
                else
                {
					hsize++;
					h[hsize] = x->val;
                    poz[x->val] = hsize;
					caract[x->val] = 1;
                    moveUp(x->val);
                }
            }
    }
}

void add_list(int x, int y, int cc)
{
    PNOD p = new NOD;
    p->val = y;
    p->cost = cc;
    p->next = list[x];
    list[x] = p;
}

void buildHeap()
{
	int i;
	for (i = 1; i <= n; ++i)
	{
		d[i] = INF;
		h[i] = i;
		poz[i] = i;
	}
	hsize = n;
	d[source] = 0;
	for (i = n / 2; i >= 1; --i)
		rebuildHeap(i);
}

void rebuildHeap(int nod) // primeste poz in heap
{
	int value = h[nod];
	int parent = nod;
	int son = parent * 2;
	while (son <= hsize)
	{
		if (son < hsize)
			if (d[h[son]] > d[h[son+1]])
				son++;
		if (d[value] > d[h[son]])
		{
			h[parent] = h[son];
			poz[h[parent]] = parent;
			parent = son;
			son = parent * 2;
		}
		else
			break;
	}
	h[parent] = value;
	poz[h[parent]] = parent;
}

void moveUp(int nod) // primeste noduri
{
	int value = h[poz[nod]];
	int son = poz[nod];
	int parent = son / 2;
	while (parent && d[value] < d[parent])
	{
		h[son] = h[parent];
		poz[h[son]] = son;
		son = parent;
		parent = son / 2;
	}
	h[son] = nod;
	poz[h[son]] = son;
}

int extractMin()
{
	int minn = h[1];
	h[1] = h[hsize];
	h[hsize] = 0;
	hsize--;
	rebuildHeap(1);
	return minn;
}