#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>

#define INF 10000009
using namespace std;

ifstream cin("distante.in");
ofstream cout("distante.out");


int main() {
	int nrgf, n, m, src, x, y, cost;
	cin>>nrgf;
	vector<bool> finaldecision(nrgf, true);
	for(int k = 0; k < nrgf; k++) {
		cin>>n>>m>>src;
		vector<vector<int> > w(n+1, vector<int>(n+1, INF));
		vector<vector<pair<int, int> > > adj_list(n+1);
		priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
		vector<int> dist(n+1, INF), distassumed(n+1,0);
		for(int i = 1; i <= n; i++) cin>>distassumed[i];

		dist[src] = 0;
		for(int i = 0; i < m; i++) {
			cin>>x>>y>>cost;
			w[x][y] = cost;
			adj_list[x].push_back(pair<int, int>(cost, y));
		}
		pq.push(pair<int, int>(0,src));
		while(!pq.empty()) {
			pair<int,int> pr = pq.top();
			pq.pop();
			int node = pr.second;
			int dst = pr.first;
			for(int i = 0; i < adj_list[node].size(); i++) {
				int nxtnode = adj_list[node][i].second;
				cost = adj_list[node][i].first;
				if(dist[nxtnode] > cost + dist[node]) {
					dist[nxtnode] = cost + dist[node];
					pq.push(pair<int,int>(cost, nxtnode));
				}
			}
		}
		for(int i = 1; i <= n && finaldecision[k]; i++) {
			if(dist[i] != distassumed[i]) finaldecision[k] = false;
		}
	}
	for(int i = 0; i < nrgf; i++) {
		if(finaldecision[i]) cout<<"DA"<<endl;
		else cout<<"NU"<<endl;
	}
	return 0;
}