#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

#define v1 vector<pair<int,int> >

const int inf=1<<30;

int *sol;
v1 *muchii;
v1 h;
int *distante;
int *viz;

void dijskstra(int n,int s){
    distante=new int[n+1];
    viz=new int[n+1];
    for(int i=1;i<n+1;i++){
        distante[i]=inf;
        viz[i]=0;
    }

        distante[s]=0;

     h.push_back(make_pair(0,s));
    make_heap(h.begin(),h.end());

    while(!h.empty()){
        int c;
        pair<int,int > p;
        p=h.front();
        pop_heap(h.begin(),h.end());
        h.pop_back();

        c=-p.first;

        if(viz[p.second]==0){
            viz[p.second]=1;
            for(v1::iterator i=muchii[p.second].begin();i<muchii[p.second].end();++i){
                if(c+(*i).second<distante[(*i).first]){
                    distante[(*i).first]=c+(*i).second;
                    h.push_back(make_pair(-distante[(*i).first],(*i).first));
                    push_heap(h.begin(),h.end());
                }
            }
        }

    }

}


int main()
{
    ifstream f("distante.in");
    ofstream g("distante.out");

    long long n,m;
    int x,y,c;
    int nrGrafuri,sursa;

    f>>nrGrafuri;
    for(int i=0;i<nrGrafuri;++i){
        f>>n>>m>>sursa;

        muchii=new v1[n+1];
        sol=new int[n+1];


        for(int j=1;j<n+1;j++){
            f>>sol[j];
        }
        for(int j=0;j<m;j++){
            f>>x>>y>>c;
            muchii[x].push_back(make_pair(y,c));
            muchii[y].push_back(make_pair(x,c));
        }
        dijskstra(n,sursa);
        int ok=0;
        for(int k=1;k<n+1;k++){
            if(sol[k]!=distante[k])ok=1;
        }
        if(ok==0)g<<"DA\n";
        else g<<"NU\n";

        delete sol;
        delete distante;
        delete viz;

    }


    return 0;
}