// 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>

#define INT_MAX       2147483640
#define NU_EXISTA_MUCHIE -100000000

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> distante_perete;
		int distanta_nod_sursa;
		for (int i = 0; i < N; i++)
		{
			in_file >> distanta_nod_sursa;
			distante_perete.push_back(distanta_nod_sursa);
		}

		GraphBellmanFord graf(N, M);

		for (int i = 0; i < M; i++)
		{
			in_file >> a >> b >> c;
			graf.adaugaMuchieCuCost(a - 1, b - 1, c);	//Scad 1 deoarece am de la 0 considerate nodurile
		}

		graf.BellmanFord(Sursa - 1, distante_perete);
	}
}