#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define INF (1 << 30)

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

vector<int> dijkstra(vector<vector<pair<int, int>>>& adj, int n, int source) {
    vector<int> d(n + 1);
    vector<int> p(n + 1);

    for (int i = 1; i <= n; i++) {
        d[i] = INF;
        p[i] = -1;
    }

    d[source] = 0;
    p[source] = 0;

    auto compare = [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    };

    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)> pq(compare);
    pq.push({source, d[source]});

    while (!pq.empty()) {
        int node = pq.top().first;
        pq.pop();

        for (pair<int, int> neigh : adj[node]) {
            if (d[neigh.first] > d[node] + neigh.second) {
                d[neigh.first] = d[node] + neigh.second;
                p[neigh.first] = node;
                pq.push(neigh);    
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        d[i] = (d[i] == INF) ? -1 : d[i];
    }

    return d;
}

int main() {
    int n;
    fin >> n;

    for (int i = 0, nodes, edges, source; i < n; i++) {
        fin >> nodes >> edges >> source;

        vector<int> exp_dist(nodes + 1);
        for (int j = 1; j <= nodes; j++) {
            fin >> exp_dist[j];
        }

        vector<vector<pair<int, int>>> adj(nodes + 1);

        for (int j = 0, u, v, cost; j < edges; j++) {
            fin >> u >> v >> cost;
            adj[u].push_back({v, cost});
        }

        vector<int> dijkstra_dist = dijkstra(adj, nodes, source);
        bool correct = true;

        for (int j = 1; j <= nodes; j++) {
            if (exp_dist[j] != dijkstra_dist[j]) {
                fout << "NU\n";
                correct = false;
                break;
            }
        }

        if (correct) {
            fout << "DA\n";
        }
    }

    return 0;
}