// BELLMAN - FORD cu coada

#include <stdio.h>
#include <queue>
using namespace std;

#define N 50000
#define M 100000
#define INF 1000000000
#define qin(x) (qc[x])
#define init_d(); for(int i=1;i<=n;++i) d[i]=INF;

struct triplet { int x, y, c; };
queue<int> q;
bool qc[N+1];
int d[N+1], dd[N+1];
FILE *fi=fopen("distante.in","r"), *fo=fopen("distante.out","w");
int n, m, s;
triplet vt[M+1];
int *la[N+1], *c[N+1];
int grad[N+1];

inline void qadd(int x)
{
	q.push(x);
	qc[x]=true;
}

inline int qget()
{
	int e = q.front();
	q.pop();
	qc[e]=false;
	return e;
}

void bellman_ford()
{
	int e,i;
	qadd(s);
	d[s]=0;
	while(!q.empty())
	{
		e=qget();
		for(i=1;i<=grad[e];++i)
		{
			if(d[la[e][i]]>d[e]+c[e][i])
			{
				d[la[e][i]]=d[e]+c[e][i];
				if(!qin(la[e][i])) qadd(la[e][i]);				
			}
		}
	}
}


void verifica()
{
	bool ok=true;
	int i;
	for(i=1;i<=n;++i)
	{
		if(dd[i]!=d[i])
		{
			ok=false;
			break;
		}
	}
	if(ok) fprintf(fo, "DA\n");
	else fprintf(fo, "NU\n");
}

void citeste()
{
	fscanf(fi, "%d%d%d", &n, &m, &s); //citesc n m s
	int i;
	for(i=1;i<=n;++i) fscanf(fi, "%d", &dd[i]); //citesc distantele calculate de bolnav
	for(i=1;i<=n;++i) grad[i]=0; //initializez grade
	for(i=1;i<=m;++i) //citesc muchiile
	{
		fscanf(fi, "%d%d%d", &vt[i].x, &vt[i].y, &vt[i].c);
		grad[vt[i].x]++;
		grad[vt[i].y]++;
	}
	for(i=1;i<=n;++i)
	{
		la[i]=new int[grad[i]+1];
		c[i]=new int[grad[i]+1];
		grad[i]=0;
	}
	int a,b,cost;
	for(i=1;i<=m;++i)
	{
		a=vt[i].x;
		b=vt[i].y;
		cost=vt[i].c;
		grad[a]++;
		grad[b]++;
		la[a][grad[a]]=b;
		la[b][grad[b]]=a;
		c[a][grad[a]]=c[b][grad[b]]=cost;
	}
}

void freeMEM()
{
	for(int i=1;i<=n;++i)
	{
		free(la[i]);
		free(c[i]);
	}
}

void rezolva_test()
{
	citeste();
	init_d();
	bellman_ford();
	verifica();
	freeMEM();
}

int main()
{
	int nrteste;
	fscanf(fi, "%d", &nrteste);
	for(int i=0;i<nrteste;++i) rezolva_test();
	fclose(fi);
	fclose(fo);
	return 0;
}