#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() 
{
    for (int i = 1; i <= n; ++i)
    {
        d[i] = INF;
        poz[i] = i;
        h[i] = i;
        //caract[i] = true;
    }
    hsize = n;
    d[source] = 0;
	for (int i = n / 2; i >= 1; --i)
        rebuildHeap(i);
}

void rebuildHeap(int nod)
{
    int parent, son, value;
    value = h[nod]; // pornim cu nodul ce trebe reasezat
    parent = nod;   // parintele e nodul (avsansam din start 1 pas in sus)
    son = 2 * parent; // fiul sau
    
    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 = 2 * parent;
        }
        else
            break;
    }
    h[parent] = value;
    poz[h[parent]] = parent;
}

void moveUp(int nod)
{
    int parent, son, value;
    value = h[poz[nod]];
    son = poz[nod];
    parent = son / 2;
    while (parent && d[h[parent]] > d[value])
    {
        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;
}