#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
 
#include <stdlib.h>
#include <queue>
#include <vector>
#include <list>
 
using namespace std;


#define IN_FILE_NAME "distante.in"
#define OUT_FILE_NAME "distante.out"

#define MAGIC_NR 0xFFFFFF

typedef struct _EDGE
{
	int dest;
	int cost;
}EDGE;

unsigned int givenDistances[50000];
unsigned int foundDistances[50000];

vector<vector<EDGE*>> Edges = vector<vector<EDGE*>>();

void InsertEdge(vector<EDGE*> *Line, int Dest, int Cost)
{
	EDGE *Edge = (EDGE*)malloc(sizeof(EDGE));
	Edge->cost = Cost;
	Edge->dest = Dest;

	Line->push_back(Edge);
}

int main()
{	
	int tests = 0, t = 0;
 
    FILE *pFin, *pFout;
 
    pFin = fopen(IN_FILE_NAME, "r");
    pFout = fopen(OUT_FILE_NAME, "w");
 	
	fscanf(pFin, "%d", &tests);
    for(t=0; t<tests; t++)
    {
		int n, m, s;
		fscanf(pFin, "%d %d %d", &n, &m, &s);

		Edges.clear();
		Edges = vector<vector<EDGE*>>(n);

		memset(givenDistances, 1, sizeof(givenDistances));
		memset(foundDistances, 1, sizeof(foundDistances));

		int i;
		for(i=0; i<n; i++)
		{
			int nr;
			fscanf(pFin, "%d", &nr);
			givenDistances[i] = nr;
		}
		s-=1;
		foundDistances[s] = 0;

		for(i=0; i<m; i++)
		{
			// Read edges
			int a,b,c;
			fscanf(pFin, "%d %d %d", &a, &b, &c);

			a-=1; b-=1; 
			InsertEdge(&(Edges[a]), b, c);
			InsertEdge(&(Edges[b]), a, c);
		}

		// Dijkstra
		EDGE *sourceEdge = new EDGE;
		sourceEdge->cost = 0;
		sourceEdge->dest = s;

		bool bFoundWrong = false;

		list<EDGE*> *Queue = new list<EDGE*>();
		int nrCompleted = 1;

		Queue->push_front(sourceEdge);
		do
		{			
			EDGE *currEdge = Queue->front();
			Queue->pop_front();
			if(bFoundWrong || nrCompleted==n)
				continue;
			int dest = currEdge->dest;
			int cost = currEdge->cost;
			if(cost > foundDistances[dest])
			{
				bFoundWrong = true;
			}
			else
			{
				int i;
				if(cost < givenDistances[dest])
				{
					bFoundWrong = true;
					break;
				}
				for(i=0; i<Edges[dest].size(); i++)
				{
					EDGE *neighbourEdge = Edges[dest][i];
					int newDest = neighbourEdge->dest;
					int newCost = neighbourEdge->cost + cost;

					if(newCost < foundDistances[newDest])
					{						
						nrCompleted++;
						foundDistances[newDest] = newCost;
						EDGE *newEdge = new EDGE();
						newEdge->dest = newDest;
						newEdge->cost = newCost;
										
						// insert sorted
						std::list<EDGE*>::iterator it;
						for (it = Queue->begin(); it != Queue->end(); it++)
						{
							EDGE*e = *it;
							if(e->cost > newCost)
								break;
						}
						Queue->insert(it, newEdge);
					}
				}
			}
			delete currEdge;				
		}while(!Queue->empty());

		bool bOk = true;
		if(bFoundWrong)
			bOk = false;
		else
		{
			for(i=0; i<n; i++)
			{
				if(foundDistances[i] != givenDistances[i])
				{
					bOk = false;
					break;
				}
			}
		}

		if(bOk)
			fprintf(pFout, "DA\n");
		else
			fprintf(pFout, "NU\n");

		delete Queue;
	}

	
	fclose(pFin);
	fclose(pFout);

	return 0;
}