#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("distante.in");
ofstream out("distante.out");
int presupus[50001];
int distante[50001];
bool compara(pair <int, int> &a, pair <int, int> &b)
{
	if (a.second > b.second) { return 1; }
	else { return 0; }
}
void rez()
{
	int i, n, m, k,x,y,z;
	vector<pair <int, int> > hip;
	vector< pair <int, int> > muchii[50001];
	pair <int, int> pereche;
	in >> n;
	in >> m;
	in >> k;
	for (i = 1;i <= n;i++)
	{
		distante[i] = 9999999;
		in >> presupus[i];
	}
	distante[k] = 0;
	for (i = 1;i <= m;i++)
	{
		in >> x;
		in >> pereche.first;
		in >> pereche.second;
		muchii[x].push_back(pereche);
	}
	for (i = 0;i < muchii[k].size();i++)
	{
		hip.push_back(muchii[k][i]);
	}
	make_heap(hip.begin(), hip.end(), compara);
	while (!hip.empty())
	{
		x = hip[0].first;
		y = hip[0].second;
		pop_heap(hip.begin(),hip.end(),compara);
		hip.pop_back();
		if (y < distante[x])
		{
			distante[x] = y;
			for (i = 0;i < muchii[x].size();i++)
			{
				pereche.first = muchii[x][i].first;
				pereche.second = muchii[x][i].second + y;
				hip.push_back(pereche);
				push_heap(hip.begin(), hip.end(), compara);
			}
		}
	}
	for (i = 1;i <= n;i++)
	{
		if (presupus[i] != distante[i])
		{
			out << "NU\n";
			return;
		}
	}
	out << "DA\n";
	return;
}
int main()
{
	int i, n;
	in >> n;
	for (i = 1;i <= n;i++)
	{
		rez();
	}
}