#include <fstream>
#define NMAX 10000
#define INF 2000000000
#define InFile "distante.in"
#define OutFile "distante.out"

using namespace std;

struct Arc {short int vf; int c;};
ifstream fin(InFile);
ofstream fout(OutFile);
Arc G[NMAX][NMAX];
int n, x0, lgh,nr;
int dmin[NMAX];
int poz[NMAX];
int h[NMAX];
int dist[NMAX];

void Citire();
void InitHeap();
void Dijkstra();
void Afisare();

int main()
{fin>>nr;
for(int i=1;i<=nr;i++)
{Citire();
InitHeap();
Dijkstra();
Afisare();}
fout.close();
return 0;
}


void AdaugaArc(int x, int y, int cost)
{
G[x][0].c++;
G[x][G[x][0].c].vf=y;
G[x][G[x][0].c].c=cost;
}


void Citire()
{int m, i, x, y, cost;

fin>>n>>m>>x0;
for(i=1;i<=n;i++)
	fin>>dist[i];
for (i=0; i<m; i++)
	{fin>>x>>y>>cost;
     AdaugaArc(x,y,cost);
	}
}

void CombHeap(int i)
//combin heapul cu radacina 2i cu cel cu radacina 2i+1 si cu vf i
{
int tata=i, aux;
int fiu=2*tata;
while (fiu<=lgh)
	{
	if (fiu<lgh && dmin[h[fiu+1]]<dmin[h[fiu]]) fiu++;
	if (dmin[h[tata]]>dmin[h[fiu]])
		{poz[h[tata]]=fiu; poz[h[fiu]]=tata;
		aux=h[tata]; h[tata]=h[fiu]; h[fiu]=aux;
		tata=fiu;
		fiu=2*tata;
		}
		else break;
	}
}

void InitHeap()
{int i, j;
for (i=1; i<=n; i++) {dmin[i]=INF; h[i]=i; poz[i]=i;}
lgh=n;
for (j=1; j<=G[x0][0].c; j++)
	dmin[G[x0][j].vf]=G[x0][j].c;
dmin[x0]=0;
for (i=n/2; i>=1; i--) CombHeap(i);
}

int ExtrageMin()
{int minim=h[1];
 h[1]=h[lgh]; lgh--; poz[h[1]]=1; poz[minim]=-1;
 CombHeap(1);
 return minim;
}

void Upgrade(int fiu)
{
int tata=fiu/2, aux;
while (tata > 0 && dmin[h[tata]] > dmin[h[fiu]])
	{
	poz[h[tata]]=fiu; poz[h[fiu]]=tata;	
    aux=h[tata]; h[tata]=h[fiu]; h[fiu]=aux; 
	fiu=tata;
	tata=fiu/2;
	}	
}

void Dijkstra()
{int i, j, vfmin;
for (i=0; i<n; i++)
	{vfmin=ExtrageMin();
     for (j=1; j<=G[vfmin][0].c; j++)
		 if (poz[G[vfmin][j].vf]!=-1) //il mai am in heap
			 if (dmin[G[vfmin][j].vf]>dmin[vfmin]+G[vfmin][j].c)
				 {dmin[G[vfmin][j].vf]=dmin[vfmin]+G[vfmin][j].c;
			     Upgrade(poz[G[vfmin][j].vf]);
				 }
	}

}	
	
void Afisare()
{
int i,ok=1;
for (i=1; i<=n; i++)
     if(dmin[i]!=dist[i])
		 ok=0;
if(ok)
	fout<<"DA";
	else fout<<"NU";
fout<<'\n';
}