#include <bits/stdc++.h>

#define f first
#define sd second

using namespace std;

FILE *F=fopen("distante.in", "r"), *G=fopen("distante.out", "w");

int t, n, m, s, v[50003], d[50003], c, x, y, nod, ok;
vector<pair<int, int> > a[50003];
vector<pair<int, int> > :: iterator it;
priority_queue<pair<int, int> > pq;
const int inf = 1000000002;
bitset<50003> w;

int main()
{
    fscanf(F, "%d ", &t);
    fscanf(F, "%d%d%d ", &n, &m, &s);
    for(int k = 0; k < t; ++ k)
    {
        for(int i = 1; i <= n; ++ i) fscanf(F, "%d ", &v[i]), d[i] = inf;
        memset(a, 0, sizeof(a));
        w = 0;
        for(int i = 0; i < m; ++ i)
        {
            fscanf(F, "%d%d%d ", &x, &y, &c);
            a[x].push_back({y, c});
            a[y].push_back({x, c});
        }
        pq.push({0, s});
        d[s] = 0;
        while(!pq.empty())
        {
            nod = pq.top().sd;
            if(w[nod]) continue;
            w[nod] = 1;
            pq.pop();
            for(it = a[nod].begin(); it != a[nod].end(); ++ it)
                if(d[nod] + (*it).sd < d[(*it).f])
                    d[(*it).f] = d[nod] + (*it).sd, pq.push({-d[(*it).f], (*it).f});
        }
        ok = 0;
        for(int i = 1; i <= n && !ok; ++ i)
            if(v[i] != d[i]) ok = 1;
        ok == 0 ? fprintf(G, "DA\n") : fprintf(G, "NU\n");
    }
    return 0;
}