#include <fstream>
#include <cstring>
#include <vector>
#define DIM 50005

using namespace std;

ifstream fin("distante.in");
ofstream fout("distante.out");

int N,M,S;
int T;
int n;
vector <pair <int,int> > v[DIM];
pair <int,int> H[DIM];
int D[DIM],dist[DIM];
void upheap(int x){
    int c=x;
    int p=c/2;
    while(p>=1 && H[p].second>H[c].second){
        swap(H[p],H[c]);
        c=p;
        p/=2;
    }
}
void downheap(int x){
    int p=x;
    int c=2*p;
    while(c<=n){
        if(c+1<=n && H[c].second>H[c+1].second)
            c++;
        if(H[p].second>H[c].second){
            swap(H[p],H[c]);
            p=c;
            c*=2;
        }
        else
            break;
    }
}
void insert(int x,int y){
    H[++n]=make_pair(x,y);
    upheap(n);
}
void delete_root(){
    H[1]=H[n];
    n--;
    downheap(1);
}
int solve(){
    memset(D,0x3f3f3f3f,sizeof(D));
    fin>>N>>M>>S;
    for(int i=1;i<=N;i++)
        fin>>dist[i];
    while(M--){
        int x,y,cost;
        fin>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
        v[y].push_back(make_pair(x,cost));
    }
    D[S]=0;
    insert(S,0);
    while(n){
        int node=H[1].first;
        int val=H[1].second;
        delete_root();
        for(std::vector <pair <int,int> >::iterator it=v[node].begin();it!=v[node].end();it++)
            if(D[it->first]>val+it->second){
                D[it->first]=val+it->second;
                insert(it->first,D[it->first]);
            }
    }
    int ok=1;
    for(int i=1;i<=N;i++){
        v[i].clear();
        if(dist[i]!=D[i])
            ok=0;
    }
    return ok;
}
int main(){
    fin>>T;
    while(T--){
        if(solve())
            fout<<"DA\n";
        else
            fout<<"NU\n";
    }
    fin.close();fout.close();
    return 0;
}