#include <fstream>
#include <iostream>
#define MAX 5000

using namespace std;



int main()
{
	int T, c, ok = 1;
	long int a, b, S, N, M;
	int *d, *dist, *starts;

	
    long **adj;
	
	
	ifstream fin("distante.in");
	ofstream fout("distante.out");

	fin >> T;
	
	for (int z = 0; z < T; z++)
	{
		fin >> N >> M >> S;
		
		starts = new int[N];
		d = new int[N];
		dist = new int[N];
		
		adj = new long*[N];
		for (long int i = 1; i <= N; i++)
			adj[i] = new long[N];


		
		for (long int j = 1; j <= N; j++)
		{
			fin >> d[j];
		}
		
		for (long int j = 1; j <= N; j++)
		{
			starts[j] = 0;
		}

		for (long int i = 1; i <= N; i++)
		{
			for (long int j = 1; j <= N; j++)
			{
				if (i == j)
					adj[i][j] = 0;
				else
					adj[i][j] = MAX;
			}
		}
			
		for (long int k = 1; k <= M; k++)
		{
			fin >> a >> b >> c;
			adj[a][b] = c;
			adj[b][a] = c;
		}

		long int min, y;
		starts[S] = 1;

		for (long int i = 1; i <= N; i++)
		{
			dist[i] = adj[S][i];
		}

		for (long int i = 1; i <= N; i++)
		{
			for (long int j = 1, min = MAX; j <= N; j++)
			{
				if ((starts[j] == 0) && (dist[j] < min))
				{
					min = dist[j];
					y = j;
				}
			}
			starts[y] = 1;
			for (long int j = 1; j <= N; j++)
			{
				if ((starts[j] == 0) && (dist[j] > dist[y] + adj[y][j]))
				{
					dist[j] = dist[y] + adj[y][j];
				}
			}
		}

		for (long int i = 1; i <= N; i++)
		{
			if (d[i] != dist[i])
			{
				ok = 0;
				break;
			}

		}

		if (ok == 1)
			fout << "DA\n";
		else
			fout << "NU\n";
		
	}

	
	
	
	return 0;
}