#include <stdio.h>
#define DIM 50110
#define INF 2100000000

struct nod {
	int v;
	int c;
	nod *adr;
};

nod *P[DIM], *q;

int D[DIM];
int Poz[DIM];
int H[DIM];
int B[DIM];

int n,m,x,y,c,i,min,dH,T,s,ok;

void down(){
	int p, c, aux;
	p = 1;
	c = 2;
	while (c<=dH) {
		if (c+1<=dH && D[H[c+1]]<D[H[c]])
			c++;
		if (D[H[p]]>D[H[c]]) {
			aux = H[p];
			H[p] = H[c];
			H[c] = aux;
			
			Poz[H[p]] = p;
			Poz[H[c]] = c;
			
			p = c;
			c = 2*p;
		} else break;
	}
}

void up(int poz) {
	int c, p, aux;
	c = poz;
	p = c/2;
	while (p && D[H[p]]>D[H[c]]) {
		aux = H[p];
		H[p] = H[c];
		H[c] = aux;
		
		Poz[H[p]] = p;
		Poz[H[c]] = c;
		
		c = p;
		p = c/2;
	}
}

int main(){
	
	FILE *f = fopen("distante.in","r");
	FILE *g = fopen("distante.out","w");
	
	fscanf(f,"%d",&T);
	
	while(T) {
	
		fscanf(f,"%d %d %d",&n, &m, &s);
		for (i=1;i<=n;i++) 
			fscanf(f,"%d",&B[i]);
		
		for (i=1;i<=m;i++) {
			fscanf(f,"%d %d %d",&x, &y, &c);
			q = new nod;
			q->v = y;
			q->c = c;
			q->adr = P[x];
			P[x] = q;
		}
		
		
		for (i=2;i<=n;i++) {
			D[i] = INF;
			Poz[i] = 0;
		}
		D[1] = 0;
		Poz[1] = 0;
		
		H[1] = 1;
		dH = 1;
		Poz[1] = 1;
		
		while (dH) {
			min = H[1];
			H[1] = H[dH];
			Poz[H[1]] = 1;
			dH--;
			
			down();
			
			q = P[min];
			while (q) {
				if (D[min]+q->c < D[q->v]) {
					D[q->v] = D[min]+q->c;
					if (Poz[q->v] == 0) {
						dH++;
						H[dH] = q->v;
						Poz[q->v] = dH;
					}
					up(Poz[q->v]);
					down();
				}
				q = q->adr;
			}
		}
		
		ok = 1;
		for (i=1;i<=n;i++)
			if (B[i]!=D[i])
				ok = 0;
		if (ok)
			fprintf(g,"DA\n");
		else
			fprintf(g,"NU\n");
		T--;
	}

	fclose(f);
	fclose(g);
	
	return 0;
}