#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)

// 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) { }
};

class Task {
public:
    void solve() {
        read_input();
        print_output();
    }

private:
    // n = numar de noduri, m = numar de muchii
    int n, m, t;
    int current;
    // adj[node] = lista de adiacenta a nodului node
    // perechea (neigh, w) semnifica arc de la node la neigh de cost w
    vector<pair<int, int>> adj[NMAX];
    vector<int> distances;
    // nodul sursa
    int source;
    vector<bool> results;

    void read_input() {
        ifstream fin("distante.in");
        fin >> t;
        results.resize(t);

        for (current = 0; current < t; current++) {
            fin >> n >> m >> source;
            distances.assign(n + 1, 0);

            for (int i = 1; i <= n; i++) {
                fin >> distances[i];
            }
            for (int i = 1, x, y, w; i <= m; i++) {
                fin >> x >> y >> w;
                adj[x].push_back({y, w});
                adj[y].push_back({x, w});
            }

            results[current] = get_result();
            // Clear adjacency list for the next graph
            for (int i = 1; i <= n; i++) {
                adj[i].clear();
            }
        }

        fin.close();
    }

    bool get_result() {
        vector<int> d(n + 1, INF);
        vector<int> p(n + 1, -1);

        // Priority queue to store (distance, node) pairs, min-heap
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        // Initialize the source node
        d[source] = 0;
        pq.push({0, source});

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

            // If the distance is already greater than the known shortest, skip processing
            if (dist > d[node]) {
                continue;
            }

            // Relaxation step
            for (const auto& edge : adj[node]) {
                int neigh = edge.first;
                int weight = edge.second;

                if (d[node] + weight < d[neigh]) {
                    d[neigh] = d[node] + weight;
                    p[neigh] = node;
                    pq.push({d[neigh], neigh});
                }
            }
        }

        // Convert unreachable nodes distances from INF to -1
        for (int i = 1; i <= n; ++i) {
            if (d[i] == INF) {
                d[i] = -1;
            }
        }

        for (int node = 1; node <= n; node++) {
            if (d[node] != distances[node]) {
                return false;
            }
        }
        return true;
    }

    void print_output() {
        ofstream fout("distante.out");

        for (int i = 0; i < t; i++) {
            if (results[i]) {
                fout << "DA\n";
            } else {
                fout << "NU\n";
            }
        }
        fout.close();
    }
};

// [ATENTIE] NU modifica functia main!
int main() {
    // * se aloca un obiect Task pe heap
    // (se presupune ca e prea mare pentru a fi alocat pe stiva)
    // * se apeleaza metoda solve()
    // (citire, rezolvare, printare)
    // * se distruge obiectul si se elibereaza memoria
    auto* task = new (nothrow) Task(); // hint: cppreference/nothrow
    if (!task) {
        cerr << "new failed: WTF are you doing? Throw your PC!\n";
        return -1;
    }
    task->solve();
    delete task;
    return 0;
}