#include <bits/stdc++.h>

using namespace std;

vector<int> Dijkstra(int n, int m, int source,vector<pair<int, int>> adj[]){

        vector<int> d(n + 1);
        vector<int> p(n + 1);
        for(int i = 1; i <= n; i++) {
        d[i] = -1; // initializam distanta la infinit
        p[i] = -1; // initializam parintele la -1
        }
   
        d[source] = 0; // distanta de la sursa la ea insasi este 0
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // coada de prioritati minima
        pq.push({0, source}); // adaugam nodul sursa cu costul 0
        
        while(!pq.empty()) {
            int u = pq.top().second;
            int d_u = pq.top().first;
            pq.pop();
        
            if(d[u] != -1 && d[u] < d_u) continue; // nodul u a fost deja extras din coada cu o distanta mai mica
            for(auto edge : adj[u]) {
                int v = edge.first;
                int w = edge.second;
                    if(d[v] == -1 || d[u] + w < d[v]) { // gasim o distanta mai buna catre nodul v prin nodul u
                        d[v] = d[u] + w;
                        p[v] = u;
                    pq.push({d[v], v});
                }
        }
    }
    return d;
}
int main(){
    ifstream f("distante.in");
    ofstream g("distante.out");

    int x,y,nr_grafuri,n,m,source;
    bool ok;
    f >> nr_grafuri;
    
    for(int t = 0; t < nr_grafuri; t++){
        f >> n >> m >> source;

        vector<int>d(n+1);
        vector<int>cp_d(n+1);
        vector<pair<int, int>> adj[n+1];
        vector <pair<int,int>>muchii;

        for(int i = 1; i <= n; i++)
            f >> d[i];
        for (int i = 1, x, y, w; i <= m; i++) {
            f >> x >> y >> w;
            adj[x].push_back({y, w});
        }
        ok = 0;
        cp_d = Dijkstra(n,m,source,adj);
        for(int i = 1; i <= n; i++){
            if(d[i] != cp_d[i])
                ok = 1;
        }
        if(ok == 1)
            g << "NU" << '\n';
        else g<< "DA" << '\n';
    }
    f.close();
    g.close();
}