#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define mx 50005
#define INF (1<<30)
using namespace std;
ifstream in("distante.in");
ofstream out("distante.out");
int DCO;
int verificare[mx];
bool v[mx];
int  d[mx];
vector < pair < int , int > > A[mx];
int x,y,c,i,n,m,s;

struct compara
{
    bool operator()(int x, int y){
            return d[x]>d[y];
    }
};
priority_queue < int ,vector< int > , compara > q;


void verificareF (){
    for(i=1;i<=n;++i){
        if(verificare[i] != d[i]) {out<<"NU"<<'\n';
        return;}
    }
    out<<"DA"<<'\n';
     return;
}

void clean()
{
    for(int i = 0 ; i <= n ; ++i)
    {
        A[i].clear();

        verificare[i] = INF;
    }


}

void Dijkstra(int sursa){
    while(!q.empty())
    {
        q.pop();
    }
    for(i=1;i<=n;i++){
        d[i]=INF;
    }
    d[sursa]=0;
    q.push(sursa);
    vector < pair < int , int > >::iterator it;
    while (!q.empty()){
        int nodcurent=q.top();
        q.pop();
        v[nodcurent]=false;
        for(it=A[nodcurent].begin() ; it!=A[nodcurent].end() ; it++){
            int vecin=it->first;
            int cost=it->second;
            if(d[vecin]>d[nodcurent]+cost){
                d[vecin]=d[nodcurent]+cost;
                    q.push(vecin);
            }
        }

    }
    verificareF();
}


int main()
{
    in>>DCO;
    while(DCO){
        in>>n>>m>>s;
        for(i=1;i<=n;++i)
            {
                in>>verificare[i];
            }
        for(i=1;i<=m;++i){
            in>>x>>y>>c;
            A[x].push_back(make_pair(y,c));
        }
        Dijkstra(s);
    clean();
        DCO--;
    }
    return 0;
}