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

using namespace std;

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

void Dijkstra(int start, vector<vector<pair<int, int>>>& vecini, vector<int>& distante_corecte, vector<bool>& vizitat, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& q)
{
	distante_corecte[start] = 0;

	q.push(make_pair(0, start));

	while (!q.empty())
	{
		int u = q.top().second; // este extras nodul cu eticheta minima din q
		q.pop();

		if (!vizitat[u]) // u tocmai a fost extras din coada, asa ca trebuie marcat ca fiind vizitat
			vizitat[u] = 1;

		else
			continue;

		for (int i = 0; i < vecini[u].size(); i++)
		{
			int v = vecini[u][i].first;
			int cost = vecini[u][i].second;

			if (distante_corecte[v] > distante_corecte[u] + cost) // relaxarea lui uv
			{
				distante_corecte[v] = distante_corecte[u] + cost;
				q.push(make_pair(distante_corecte[v], v));
			}
		}
	}
}

void rezolva_problema ()
{
	int n, m, start, ok;

	f >> n >> m >> start;

	vector<int>distante_Bronzarel; // vector in care stochez distantele calculate de Bronzarel
	vector<vector<pair<int, int>>>vecini; // liste de adiacenta in care stochez si lungimea
	vector<int>distante_corecte; // vector in care este stocat costul minim al unui drum de la u la v, descoperit pana la acel moment 
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q; // coada de prioritati in care salvez nodurile neselectate inca
	vector<bool>vizitat; // vector in care sunt marcate varfurile vizitate (daca un varf este vizitat => nu se afla in Q)

	distante_Bronzarel.resize(n + 1);
	vecini.resize(n + 1);
	distante_corecte.resize(n + 1, 1000000);
	vizitat.resize(n + 1, 0);
	

	for (int i = 1; i <= n; i++)
		f >> distante_Bronzarel[i];

	for (int i = 1; i <= m; i++)
	{
		int a, b, c;

		f >> a >> b >> c;

		vecini[a].push_back(make_pair(b, c));
		vecini[b].push_back(make_pair(a, c));
	}

	Dijkstra(start, vecini, distante_corecte, vizitat, q);

	ok = 1;

	for (int i = 1; i <= n; i++)
		if (distante_corecte[i] != distante_Bronzarel[i])
		{
			g << "NU" << "\n";

			ok = 0;

			break;
		}

	if (ok)
		g << "DA" << "\n";
}

int main()
{
	int nr_grafuri;

	f >> nr_grafuri;

	for (int i = 1; i <= nr_grafuri; i++)
		rezolva_problema();

	return 0;
}