#include<fstream>
#include<vector>
#include<queue>
using namespace std;

ifstream f("distante.in");
ofstream g("distante.out");

#define nmax 50002
#define INF 100000001
typedef struct noduri{int vec,dist;};
noduri aux;
vector <noduri> v[nmax];
queue <int> Q;
int n,m,t,S,d[nmax],l[nmax],D[nmax];
bool inQ[nmax];

void afisare()
{
	int i;
	for(i=1;i<=n;i++)
		if(d[i]!=D[i])
		{
			g<<"NU"<<'\n';
			return;
		}
	g<<"DA"<<'\n';
	return;
}
int main()
{
	f>>t;
	int i;
	for(;t;--t)
	{
		f>>n>>m>>S;
		for(i=1;i<=n;i++)
		{
			f>>D[i]; d[i]=INF;
			l[i]=0;
			while(!v[i].empty()) v[i].pop_back();
		}
		d[S]=0;
		for(;m;--m)
		{
			f>>i>>aux.vec>>aux.dist;
			v[i].push_back(aux);
		}
		for(i=1;i<=n;i++) l[i]=v[i].size();
		Q.push(S); inQ[S]=1;
		while(!Q.empty())
		{
			S=Q.front(); inQ[S]=0; Q.pop();
			for(i=0;i<l[S];i++)
				if(d[v[S][i].vec]>d[S]+v[S][i].dist)
				{
					d[v[S][i].vec]=d[S]+v[S][i].dist;
					if(!inQ[v[S][i].vec])
					{
						Q.push(v[S][i].vec);
						inQ[v[S][i].vec]=1;
					}
				}
		}
		afisare();
	}
}