#include <bits/stdc++.h>
#define INF 0x3F3F3F3F
#define N 50000
using namespace std;

ifstream fin ("distante.in");
ofstream fout ("distante.out");
class heap {
public:
    int nod, dist;
    heap (int i, int j) {nod = i, dist = j;}
    bool operator < (const heap &x) const {return dist > x.dist;}
};

array <int, N+1> dist, given;
bool Dijkstra () {
    vector <pair <int, int>> G[N+1];
    int n, m, root;
    fin >> n >> m >> root;

    int i, j, c;
    for (i=1; i<=n; ++i)
        fin >> given[i];

    for (; m; --m) {
        fin >> i >> j >> c;
        G[i].emplace_back(j, c);
        G[j].emplace_back(i, c);
    }

    fill(&dist[1], &dist[n+1], INF);
    dist[root] = 0;
    
    priority_queue <heap> PQ;
    PQ.emplace(root, 0);
    
    while (!PQ.empty()) {
        heap save = PQ.top();
        PQ.pop();

        if (dist[save.nod] == save.dist)
            if (dist[save.nod] < given[save.nod])
                return 0;
            else
                for (auto it: G[save.nod])
                    if (dist[it.first] > save.dist + it.second)
                        dist[it.first] = save.dist + it.second,
                        PQ.emplace(it. first, save.dist + it.second);
    }
    return 1;
}

int main () {
    int t;
    fin >> t;
    for (; t; --t)
        fout << (Dijkstra() ? "DA\n" : "NU\n");
    return 0;
}