#include <stdio.h>
#include <set>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 50001

using namespace std;

vector <pair<unsigned int, unsigned int> > v[MAX_N];
set <pair<unsigned int, unsigned int> > s;
unsigned int dist[MAX_N];
unsigned int T, M, N, S;
unsigned int bronz_dist[MAX_N];

int main()
{
	FILE *fp_in, *fp_out;
	fp_in = fopen("distante.in", "r");
	fp_out = fopen("distante.out", "w");
	fscanf(fp_in, "%d", &T);
	unsigned int i, j, k, a, b, c;
	for (i = 1; i <= T; i++)
	{
		fscanf(fp_in, "%d%d%d", &N, &M, &S);
		for (j = 1; j <= N; j++)
			fscanf(fp_in, "%d", &bronz_dist[j]);
		for (j = 0; j < M; j++)
		{
			fscanf(fp_in, "%d%d%d", &a, &b, &c);
			v[a].push_back(make_pair(b, c));
		}
		memset(&dist, '\xff', sizeof(dist));
		s.insert(make_pair(0, S));
		unsigned int nod, len;
		while (!s.empty())
		{
			nod = s.begin()->second;
			len = s.begin()->first;
			s.erase(s.begin());
			if (dist[nod] > len)
			{
				dist[nod] = len;
				for (j = 0; j < v[nod].size(); j++)
					if (len + v[nod][j].second < dist[v[nod][j].first])
						s.insert(make_pair(len + v[nod][j].second, v[nod][j].first));
			}
		}
		for (j = 1; j <= N; j++)
			v[j].clear();
		s.clear();
		bool chk = true;
		for (j = 1; j <= N; j++)
			if (dist[j] != bronz_dist[j])
			{
				chk = false;
				break;
			}
		if (chk)
			fprintf(fp_out, "DA");
		else
			fprintf(fp_out, "NU");
        if (i != T)
            fprintf(fp_out, "\n");
	}
	fclose(fp_in);
	fclose(fp_out);
    return 0;
}