#include<fstream>
#include<vector>
using namespace std;

const int INF = 30000000;

bool dijkstra();
void push(int value);
void pop();
void reconst(int value);

vector<pair<int, int> > x[50001];

int t, n, m, s;
int cost[50001], heap[50001], h, him[50001], pos[50001];
bool sel[50001];

int main()
{
	ifstream fin("distante.in");
	ofstream fout("distante.out");
	fin >> t >> n >> m >> s;
	while (t--)
	{
		memset(sel, 0, sizeof(sel));
		
		for (int i = 1; i <= n; ++i)
		{
			fin >> him[i];
			x[i].clear();
		}
		for (int i = 1, a, b, c; i <= m; ++i)
		{
			fin >> a >> b >> c;
			x[a].push_back(make_pair(b, c));
			x[b].push_back(make_pair(c, b));
		}
		bool result = dijkstra();
		if (result == true)
			fout << "DA\n";
		else
			fout << "NU\n";
	}
}

bool dijkstra()
{
	h = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (i == s)
			cost[i] = 0;
		else
			cost[i] = INF;
		push(i);
	}
	for (int pas = 1; pas < n; ++pas)
	{
		int k = heap[1];
		sel[k] = true;
		pop();
		
		for (int i = 0; i < (int)x[k].size(); ++i)
			if (!sel[x[k][i].first] && cost[k] + x[k][i].second < cost[x[k][i].first])
			{
				cost[x[k][i].first] = cost[k] + x[k][i].second;
				reconst(i);
			}
	}
	for (int i = 1; i <= n; ++i)
		if (cost[i] != him[i])
			return false;
	return true;
}

void push(int value)
{
	heap[++h] = value;
	pos[value] = h;
	int son = h, fat = h >> 1;
	while (fat && cost[heap[son]] < cost[heap[fat]])
	{
		swap(heap[son], heap[fat]);
		pos[heap[son]] = fat;
		pos[heap[fat]] = son;
		
		son >>= 1;
		fat >>= 1;
	}
}

void pop()
{
	pos[heap[h]] = 1;
	heap[1] = heap[h--];
	
	int fat = 1, son = 2;
	while (son <= h)
	{
		if (son < h && cost[heap[son]] > cost[heap[son + 1]])
			++son;
		if (cost[heap[son]] < cost[heap[fat]])
		{
			swap(heap[son], heap[fat]);
			pos[heap[son]] = fat;
			pos[heap[fat]] = son;
			
			fat = son;
			son <<= 1;
		}
		else
			break;
	}
}

void reconst(int value)
{
	int son = value, fat = value >> 1;
	while (fat && cost[heap[son]] < cost[heap[fat]])
	{
		swap(heap[son], heap[fat]);
		pos[heap[son]] = fat;
		pos[heap[fat]] = son;
		
		son >>= 1;
		fat >>= 1;
	}
}