#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("distante.in");
ofstream fout("distante.out");

const int NMAX = 50001;
const int oo = (1 << 30);
int n, m, s, t;
int D[NMAX];
int solutie[NMAX];
bool InCoada[NMAX];

struct ComparaDist
{
	bool operator() (int x, int y)
	{
		return D[x] > D[y];
	}
};
priority_queue <int, vector <int>, ComparaDist > Coada;
vector < pair < int, int > > v[NMAX];

void citire()
{
	fin >> n >> m >> s;
	for (int i = 1; i <= n; i++)
		fin >> solutie[i];
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		fin >> x >> y >> z;
		v[x].push_back(make_pair(y, z));
		v[y].push_back(make_pair(x, z));
	}
}

void Afisare()
{
	int i;
	for (i = 1; i <= n; i++)
		if (D[i] != solutie[i]) fout << "NU", i = n + 2;
	if (i == n + 1)
		fout << "DA";
}

void Dijkstra(int NodStart)
{
	for (int i = 1; i <= n; i++)
		D[i] = oo;
	D[NodStart] = 0;
	Coada.push(NodStart);
	InCoada[NodStart] = true;
	while (!Coada.empty())
	{
		int NodActual = Coada.top();
		Coada.pop();
		InCoada[NodActual] = false;
		for (auto i : v[NodActual])
		{
			int Vecin = i.first;
			int Cost = i.second;
			if (D[NodActual] + Cost < D[Vecin])
			{
				D[Vecin] = D[NodActual] + Cost;
				if (InCoada[Vecin] == false)
				{
					Coada.push(Vecin);
					InCoada[Vecin] = true;
				}
			}

		}
	}
}

void curatare()
{
	memset(D, 0, sizeof(D));
	for (int i = 1; i <= n; i++)
		v[i].clear();
}
int main()
{
	fin >> t;
	for (int i = 1; i <= t; i++)
	{
		citire();
		Dijkstra(s);
		Afisare();
		curatare();
		fout << endl;
	}
	return 0;
}