#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 nr_grafuri, n, m, source;
    f >> nr_grafuri;

    while (nr_grafuri--) {
        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});
        }

        cp_d = Dijkstra(n, m, source, adj);
        bool ok = true;
        for (int i = 1; i <= n; i++) {
            if (d[i] != cp_d[i]) {
                ok = false;
                break;
            }
        }
        if (ok)
            g << "DA\n";
        else
            g << "NU\n";
    }
    f.close();
    g.close();
    return 0;
}