#include <cstdio>
#include <fstream>
#define dim 50001
#define infinit 1 << 30

using namespace std;

ifstream fin ("distante.in");
ofstream fout ("distante.out");

struct nod {
	int x, c;
	nod *urm;
};
nod *p[dim];

int n, m, k = 1;

int d[dim], heap[dim], poz[dim];
int vi,sip[dim];

void add(nod *&p, int y, int c) {
	nod *q = new nod;
	q -> x = y;
	q -> c = c;
	q -> urm = p;
	p = q;
}

void citire() {
    fin>>n>>m>>vi;

        for (int i=1;i<=n;i++)
        {
            fin>>sip[i];
            p[i]=NULL;
        }

    int x, y, c;
	for ( int i = 0; i < m; i++ ) {
		fin>>x>>y>>c;
		add(p[x], y, c);
		add(p[y], x, c);
	}
}

void intersch(int t, int c) {
	int aux = heap[t];
	heap[t] = heap[c];
	heap[c] = aux;
}

void in_sus(int c) {
	while ( c > 1 )  {
		int t = c >> 1;
		if ( d[heap[t]] <= d[heap[c]] )
			break;
		poz[heap[c]] = t;
		poz[heap[t]] = c;
		intersch(t, c);
		c = t;
	}
}

void in_jos(int t){
	while ( t <= k ) {
		int c = t;
		if ( (t << 1) > k )
			return;
		c = t << 1;
		if ( c + 1 <= k )
			if ( d[heap[c+1]] < d[heap[c]])
				c++;
		if (d[heap[t]]<= d[heap[c]])
			return;
		poz[heap[t]] = c;
		poz[heap[c]] = t;
		intersch(t, c);
		t = c;
	}
}

void init() {
	for ( int i = 1; i <= n; i++ ){
		d[i] = infinit;
		poz[i] = -1;
		heap[i] = i;
	}
	d[vi] = 0;
	poz[1] = 1;
	poz[vi]=0;
	heap[1] = vi;
}

void dijkstra() {
    k=1;
	init();
	while ( k ) {
		int min = heap[1];
		intersch(1, k);
		poz[heap[1]] = 1;
		k--;
		in_jos(1);
		for (nod *q = p[min]; q; q = q->urm) {
			if (d[q->x] > d[min] + q->c ) {
				d[q -> x] = d[min] + q->c;
				if ( poz[q->x] != -1 )
					in_sus(poz[q->x]);
				else {
					heap[++k] = q->x;
					poz[heap[k]] = k;
					in_sus(k);
				}
			}
		}
	}
}
void afisare()
{
        int ok=0;
    for (int i=1;i<=n;i++)
        if (d[i]==infinit)
        {
                if (sip[i]!=0)
            {
                    ok=1;
                break;
            }
        }
        else
            if (sip[i]!=d[i])
            {
                    ok=1;
                break;
            }
        if (ok)
            fout<<"NU";
        else
            fout <<"DA";
    fout<<"\n";
}

int main() {
    int t=0;
    fin>>t;
    while(t)
    {
        citire();
        dijkstra();
        afisare();
        t--;
    }
	return 0;
}