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

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

 private:
    int t, n, m, s;

    vector<int> toVerify;
    vector<vector<pair<int, int>>> adj;

    vector<string> results;

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

        results.reserve(t);

        for (int i = 0; i < t; ++i) {
            fin >> n >> m >> s;

            toVerify.resize(n + 1);

            for (int j = 1; j <= n; ++j) {
                fin >> toVerify[j];
            }

            adj.assign(n + 1, vector<pair<int, int>>());

            for (int j = 0, a, b, c; j < m; ++j) {
                fin >> a >> b >> c;
                adj[a].push_back({b, c});
                adj[b].push_back({a, c});
            }

            results.push_back(get_result());
        }
    }

    string get_result() {
        vector<int> dist(n + 1, INT32_MAX);

        // nodurile sunt sortate crescator in pq dupa distanta fata de sursa
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        dist[s] = 0;
        pq.push({0, s}); // by default un pq in cpp cu perechi se ia dupa first

        while (!pq.empty()) {
            auto [_, node] = pq.top();
            pq.pop();

            for (const auto& [neigh, w] : adj[node]) {
                if (dist[node] + w < dist[neigh]) {
                    dist[neigh] = dist[node] + w;
                    pq.push({dist[neigh], neigh});
                }
            }
        }

        for (int i = 1; i <= n; ++i) {
            if (toVerify[i] != dist[i]) {
                return "NU";
            }
        }

        return "DA";
    }

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

        for (auto& result : results) {
            fout << result << "\n";
        }

        fout.close();
    }
};


int main() {
    auto* task = new (nothrow) Task();

    if (!task) {
        cerr << "new failed!\n";
        return -1;
    }

    task->solve();
    delete task;

    return 0;
}