#include <bits/stdc++.h>

using namespace std;

ifstream f("distante.in");
ofstream g("distante.out");

const int INF = 1e9;
 
vector <pair <int, int>> adj[50001];
set <pair <int, int>> q;
 
int a[50001], d[50001], p[50001];
int T, N, M, S;

bool dijkstra(int s) {
	for(int i = 1;i <= N;i++)
		d[i] = INF, p[i] = -1;

	set <pair <int, int>> q;
	q.insert({0, s});
	d[s] = 0;

    while(!q.empty()){
    	int v = q.begin() -> second;
    	q.erase(q.begin());
 
    	for(auto edge : adj[v]){
    		int to = edge.first;
    		int len = edge.second;
 
    		if(d[v] + len < d[to]){
    			q.erase({d[to], to});
    			d[to] = d[v] + len;
    			p[to] = v;
    			q.insert({d[to], to});
    		}
    	}
    }

    for(int i = 1;i <= N;i++)
    	if(d[i] == INF) d[i] = 0;

    for(int i = 1;i <= N;i++)
    	if(d[i] != a[i]) return 0;
    return 1;
}

void solve(){
	f >> N >> M >> S;
	for(int i = 1;i <= N;i++)
		f >> a[i], adj[i].clear();

	while(M--){
    	int x, y, val;
    	f >> x >> y >> val;
    	adj[x].emplace_back(y, val);
    	adj[y].emplace_back(x, val);
    }

    g << (dijkstra(S)? "DA\n" : "NU\n");
}

int main(){
	f >> T;
	while(T--)
		solve();
}