#include <bits/stdc++.h>

int dist[50000];

int best[50000];

std::vector<int> v[50000][2];

std::priority_queue< std::pair<int, int> > h;

void reset(){
    for(int i=0;i<50000;i++){
        best[i]=1;
        v[i][0].clear();
        v[i][1].clear();
    }
}

int main()
{
    int t,n,m,k,i,a,b,c,rsp,nd,val,x,coun,val2,nd2;
    FILE*fi,*fo;
    fi=fopen("distante.in","r");
    fo=fopen("distante.out","w");
    fscanf(fi,"%d",&t);
    for(int q=0;q<t;q++){
        reset();
        fscanf(fi,"%d%d%d",&n,&m,&k);
        k--;
        for(i=0;i<n;i++)
        {
            fscanf(fi,"%d",&dist[i]);
        }
        for(i=0;i<m;i++){
            fscanf(fi,"%d%d%d",&a,&b,&c);
            c=-c;
            a--;
            b--;
            v[a][0].push_back(b);
            v[a][1].push_back(c);
            v[b][0].push_back(a);
            v[b][1].push_back(c);
        }
        h.push({0,k});
        coun=0;
        x=1;
        while(h.empty()==0 && x==1){
            nd=h.top().second;
            if(best[nd]==1){
                coun++;
                val=h.top().first;
                best[nd]=val;
                for(i=0;i<v[nd][0].size() && x==1;i++){
                    val2=v[nd][1][i]+val;
                    nd2=v[nd][0][i];
                    if(-val2==dist[nd2])
                        h.push({val2, nd2});
                    else if(-val2<dist[nd2])
                        x=0;
                }
            }
            h.pop();
        }
        if(x==1 && coun==n)
            fprintf(fo,"DA\n");
        else fprintf(fo,"NU\n");
    }
    fclose(fi);
    fclose(fo);
    return 0;
}