#include <cstdio>
#include <vector>
using namespace std;

vector < pair <int, int> > v[50005];
int dp[50005], heap[50005], pos[50005], f[50005], ch;
bool vis[50005];
const int INF = 1<<30;

inline void swap(int &x, int &y){
    x ^= y ^= x ^= y;
}

void ascend(int p){
    int ax;
    while(p != 1 && dp[heap[p]] < dp[heap[p>>1]]){
        swap(pos[heap[p]], pos[heap[p>>1]]);
        swap(heap[p], heap[p>>1]);
        p >>= 1;
    }
}

void descend(int p){
    int mn1, mn2;
    while(p <= ch){
        mn1 = INF;
        mn2 = INF;
        if((p<<1) <= ch){
            mn1 = dp[heap[p<<1]];
        }
        if((p<<1)+1 <= ch){
            mn2 = dp[heap[(p<<1)+1]];
        }
        if(mn1 < mn2){
            swap(pos[heap[p<<1]], pos[heap[p]]);
            swap(heap[p<<1], heap[p]);
            p = p<<1;
        }else{
            if(mn2 == INF){
                break;
            }
            swap(pos[heap[(p<<1)+1]], pos[heap[p]]);
            swap(heap[(p<<1)+1], heap[p]);
            p = (p<<1)+1;
        }
    }
    swap(pos[heap[ch]], pos[heap[p]]);
    swap(heap[p], heap[ch]);
    pos[heap[ch]] = 0;
    heap[ch] = 0;
    ch--;
}

int main(){
    freopen("distante.in", "r", stdin);
    freopen("distante.out", "w", stdout);
    int n,m,i,x,y,c,test,t,s;
    scanf("%d", &t);
    for(test = 1;test <= t;test++){
        scanf("%d %d %d", &n, &m, &s);
        for(i = 1;i <= n;i++){
            scanf("%d", &f[i]);
        }
        for(i = 1;i <= m;i++){
            scanf("%d %d %d", &x, &y, &c);
            v[x].push_back({y, c});
        }
        for(i = 0;i <= n;i++){
            dp[i] = INF;
        }
        dp[s] = 0;
        heap[++ch] = s;
        int id;
        while(ch){
            id = heap[1];
            vis[id] = 1;
            for(auto it : v[id]){
                if(dp[it.first] > dp[id] + it.second){
                    dp[it.first] = dp[id] + it.second;
                    if(pos[it.first] == 0){
                        heap[++ch] = it.first;
                        pos[it.first] = ch;
                    }
                    ascend(pos[it.first]);
                }
            }
            descend(1);
        }
        bool ok = true;
        for(i = 1;i <= n;i++){
            ok &= (f[i] == (dp[i] == INF ? 0 : dp[i]));
        }
        if(ok == true){
            printf("DA");
        }else{
            printf("NU");
        }
        printf("\n");
        for(i = 1;i <= n;i++){
            pos[i] = 0;
            heap[i] = 0;
            vis[i] = 0;
            v[i].clear();
        }
    }
    return 0;
}