#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> v[50001];
int dist[50001], n, m, t, s;

bool dijkastra(const int& s)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> H;

	int d[50001];

	memset(d, 0x3f3f3f3f, sizeof(d));

	d[s] = 0;

	for (H.push({ d[s], s }); !H.empty();)
	{
		int cNod = H.top().second;
		int cDist = H.top().first;
		H.pop();

		if (cDist != d[cNod])
			continue;

		for (pair<int, int> pp : v[cNod])
		{
			int nNod = pp.first;
			int nDist = pp.second;

			long s = cDist + nDist;

			if (s < d[nNod])
			{
				d[nNod] = s;
				H.push({ s, nNod });
			}
		}
	}

	for (int i = 0; i < n; ++i)
		if (dist[i] != d[i])
			return false;

	return true;
}

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


	fin >> t;

	for (int i = 0; i < t; ++i)
	{
		int a, b, c;
		fin >> n >> m >> s;
		--s;
		for (int i = 0; i < n; ++i)
			fin >> dist[i];

		for (int j = 0; j < m; ++j)
		{
			fin >> a >> b >> c;
			--a;
			--b;
			v[a].push_back({ b, c });
			v[b].push_back({ a, c });
		}

		fout << (dijkastra(s) ? "DA\n" : "NU\n");

		for (int i = 0; i < n; ++i)
			v[i].clear();
	}

	fin.close();
	fout.close();

	return 0;
}