#include <fstream>

/////////////////////
#include <vector>
////////////////////

#define NMAX 50008
#define INF 2000000000
#define InFile "distante.in"
#define OutFile "distante.out"

using namespace std;
ifstream fin(InFile);
ofstream fout(OutFile);

struct Arc {unsigned short int vf; int c;};

///////////////////////
vector <Arc> G[NMAX];
//////////////////////

int n, x0, lgh, T, ok1;
int dmin[NMAX], gresit[NMAX];
int poz[NMAX];
int h[NMAX];

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

int main()
{
Citire();
fin.close();
fout.close();
return 0;
}

void Citire()
{
  int m, i, x, j;
  Arc crt;
  fin>>T;
  for(j=1; j<=T; j++)
  {
    ok1=0;
    fin>>n>>m>>x0;
    for(i=1; i<=n; i++) fin>>gresit[i];
    for (i=0; i<m; i++)
    {
      fin>>x>>crt.vf>>crt.c;
      G[x].push_back(crt);
    }
    InitHeap();
    Dijkstra();
    Afisare();
  }
}

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=0; j<G[x0].size(); 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=0; j<G[vfmin].size(); 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;
for (i=1; i<=n; i++)
	if(dmin[i]==gresit[i]) ok1++;
if(ok1==n) fout<<"DA";
  else fout<<"NU";
fout<<'\n';
}