// http://infoarena.ro/problema/distante
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;

struct stuff {
	int from,to,cost;
};

struct myStruct {
	int startNode,nrNodes,nrEdges;
	vector<int> distance;
	list<stuff> edge;
};

int nrGraphs;
list<myStruct> graph;

void read();
void write();
	bool canBeImproved(list<myStruct>::iterator input);
	bool canBeAchieved(list<myStruct>::iterator input);

int main() {
	read();
	write();

	return (0);
}

void read() {
	ifstream in("distante.in");
	int c;

	in >> nrGraphs;

	for(int step=1;step<=nrGraphs;step++) {
		myStruct tempGraph;

		in >> tempGraph.nrNodes >> tempGraph.nrEdges >> tempGraph.startNode;

		for(int i=1;i<=tempGraph.nrNodes;i++) {
			in >> c;
			tempGraph.distance.push_back(c);
		}

		for(int i=1;i<=tempGraph.nrEdges;i++) {
			stuff tempEdge;
			in >> tempEdge.from >> tempEdge.to >> tempEdge.cost;

			tempGraph.edge.push_back(tempEdge);
		}

		graph.push_back(tempGraph);
	}

	in.close();
}

void write() {
	ofstream out("distante.out");

	list<myStruct>::iterator currentGraph;
	for(currentGraph=graph.begin();currentGraph!=graph.end();currentGraph++)
		if(currentGraph->distance.at(currentGraph->startNode-1))
			out << "NU\n";
		else
			if(canBeImproved(currentGraph))
				out << "NU\n";
			else
				if(canBeAchieved(currentGraph))
					out << "DA\n";
				else
					out << "NU\n";

	out.close();
}

bool canBeImproved(list<myStruct>::iterator input) {
	list<stuff>::iterator currentEdge;

	for(currentEdge=input->edge.begin();currentEdge!=input->edge.end();currentEdge++)
		if(input->distance.at(currentEdge->to-1) > input->distance.at(currentEdge->from) + currentEdge->cost) {
			cout << "Venim de la " << currentEdge->from << " distanta este " << input->distance.at(currentEdge->from-1) << endl;
			cout << "Mergem la " << currentEdge->to << " unde distata este " << input->distance.at(currentEdge->to-1)  << endl;
			cout << "Costul este " << currentEdge->cost << endl << endl;


			return true;
		}

	return false;
}

bool canBeAchieved(list<myStruct>::iterator input) {
	

	return true;
}