#include <bits/stdc++.h>
using namespace std;

// numarul maxim de noduri
#define NMAX 50005

// valoare mai mare decat orice distanta din graf
#define INF (1 << 30)

ifstream fin("distante.in");
ofstream fout("distante.out");

class Compare {
public:
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        return a.second > b.second;
    }
};

// structura folosita pentru a stoca distanta, cat si vectorul de parinti
// folosind algoritmul Dijkstra
struct DijkstraResult {
    vector<int> d;
    vector<int> p;

    DijkstraResult(const vector<int>& d, const vector<int>& p)
        : d(d)
        , p(p) { }
};

int main() {
    int n, m;
    // adj[node] = lista de adiacenta a nodului node
    // perechea (neigh, w) semnifica arc de la node la neigh de cost w
    // nodul sursa
    int number = 0;
    int source;
    fin >> number;
    fin >> n >> m >> source;
    
    while (number) {
        vector<int> result(n + 1);
        for (int i = 1; i <= n; i++) {
            fin >> result[i];
        }
        
        vector<pair<int, int>> adj[NMAX];
        for (int i = 1, x, y, w; i <= m; i++) {
            fin >> x >> y >> w;
            adj[x].push_back({y, w});
        }

    
        vector<int> d(n + 1, INF);
        vector<int> p(n + 1, INF);
        
    
        priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
    
        d[source] = 0;
    
        pq.push({source, d[source]});
    
        while(!pq.empty()) {
            pair<int, int> node = pq.top();
            pq.pop();
    
            for(pair<int, int> neigh : adj[node.first]) {
                if (d[node.first] + neigh.second < d[neigh.first]) {
                    d[neigh.first] = d[node.first] + neigh.second;
                    p[neigh.first] = node.first;
    
                    pq.push({neigh.first, d[neigh.first]});
                }
            }
        }
    
        for (int i = 1; i <= n; i++) 
            if (d[i] == INF)
                d[i] = -1;
        int ok = 0;
        for (int i = 1; i <= n; i++) {
            if (d[i] != result[i]) {
                fout << "NU";
                ok = 1;
                break;
            }
        }
        if (ok == 0)
            fout << "DA";
        number--;
        if (number != 0)
            fout << endl;
    }

    
}