// Graph.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <fstream>
#include <limits.h>
#include <string.h>


using namespace std;
fstream in_file;
fstream out_file;

/*

// o structura pentru muchiile din bellman ford
struct BFMuchie {
	int sursa;
	int destinatie;
	int cost;
};

class GraphBellmanFord
{
public:
	// Constructor, primim numarul de varfuri si de muchii ale grafului
	GraphBellmanFord(int Varfuri, int Muchii)
	{
		this->V = Varfuri;
		this->M = Muchii;
	}
	~GraphBellmanFord() {}

	void adaugaMuchieCuCost(int sursa, int destinatie, int cost)
	{
		BFMuchie muchie;
		muchie.sursa = sursa;
		muchie.destinatie = destinatie;
		muchie.cost = cost;
		muchii.push_back(muchie);
	}


	// Functia ce gaseste distantele minime de la nodul sursa la celelalte, functia detecteaza si ciclul negativ
	// distante pereti sunt distantele lui Bronzarel
	void BellmanFord(int src, vector<int> &distante_pereti)
	{
		vector<int> distanta;

		// Initializam distanta de la sursa la restul ca infinit, apoi distanta pana la sursa ca 0
		for (int i = 0; i < V; i++)
			distanta.push_back(INT_MAX);
		distanta[src] = 0;

		// Relaxam muchiile de v-1 ori  deoarece putem avea cel mult v-1 muchii intre sursa si o destinatie
		for (int i = 1; i <= V - 1; i++) {
			for (int j = 0; j < M; j++) {
				int u = muchii[j].sursa;
				int v = muchii[j].destinatie;
				int cost = muchii[j].cost;
				if (distanta[u] != INT_MAX && distanta[u] + cost < distanta[v])
					distanta[v] = distanta[u] + cost;
			}
		}

		// Cautam cicluri negative. Pasul de mai sus garanteaza distantele daca nu avem cicluri negative. 
		// Daca acum obtinem un cost mai mic => avem cicluri negative
		for (int i = 0; i < M; i++) {
			int u = muchii[i].sursa;
			int v = muchii[i].destinatie;
			int cost = muchii[i].cost;
			if (distanta[u] != INT_MAX && distanta[u] + cost < distanta[v])
			{
				out_file << "NU\n";
				return; // Daca am gasit un ciclu negativ, ne oprim dupa ce afisam mesajul
			}
		}

		for (int i = 1; i < V; i++)
		{
			if (distanta[i] != distante_pereti[i])
			{
				out_file << "NU\n";
				return;
			}
		}

		out_file << "DA\n";
		return;
	}

private:
	int V;	// Nr de varfuri
	int M;	// Nr de Muchii
	vector<BFMuchie> muchii;
};
*/

int main()
{
	in_file.open("distante.in");
	out_file.open("distante.out", ios::out);

	int nr_grafuri;

	in_file >> nr_grafuri;

	for (int i = 0; i < nr_grafuri; i++)
	{
		int N, M, Sursa;
		int a, b, c;	//Muchie cu costul c intre a si b
		in_file >> N >> M >> Sursa;

		vector<int> distanta;
		int distanta_nod_sursa;
		for (int i = 0; i < N; i++)
		{
			in_file >> distanta_nod_sursa;
			distanta.push_back(distanta_nod_sursa);
		}

		bool exista_graf = true;

		if (distanta[Sursa - 1] != 0)
		{
			exista_graf = false;
		}

		for (int i = 0; i < M; i++)
		{
			in_file >> a >> b >> c;
			if (distanta[a - 1] + c < distanta[b - 1] || distanta[b - 1] + c < distanta[a - 1])
			{
				exista_graf = false;
			}
		}

		if (exista_graf)
		{
			cout << "DA\n";
		}
		else
		{
			cout << "NU\n";
		}

	}
}