#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

typedef pair<int,int> pii;


const int INF = 2000000000;
const int NMAX = 50002;
int t;
vector<int> Ad[NMAX];
vector<int> Cost[NMAX];

int d[NMAX];
bool in_h[NMAX];
int distances[NMAX];

void Do(int N,int M, int S)
{
    bool prop=true;
    priority_queue <pii, vector<pii>, greater<pii>> Heap;
    for(int i=1; i<=N; ++i)
        d[i]=INF;
    d[S]=0;
    int nod;
    Heap.push( make_pair(0,S) );

    while( !Heap.empty())
    {
        nod = Heap.top().second;
        Heap.pop();
        if( in_h[nod]) continue;
        else in_h[nod] = true;

        for(int i = 0; i < Ad[nod].size(); ++i)
        {
            int w = Ad[nod][i];

            if(d[nod] + Cost[nod][i] < d[w])
            {
                d[w] = d[nod] + Cost[nod][i];
                Heap.push(make_pair( d[w],w ));
            }
        }
    }
    for(int i=1; i<=N; ++i)
    {
            if(d[i]==INF)
            {
                if(distances[i]!=0)
                {
                    prop=false;
                    break;
                }
            }
            else if(d[i]!=distances[i])
                 {
                    prop=false;
                    break;
                 }
    }
    if(prop==true)
        fout<<"DA"<<"\n";
    else fout<<"NU"<<"\n";
}

void Read(int N,int M, int S)
{
    for(int i=1; i<=N; ++i)
        fin>>distances[i];
    for(int i=1; i<=M; ++i)
    {
        int a,b,d;
        fin >> a>> b>>d;
        Ad[a].push_back(b);
        Cost[a].push_back(d);
    }
    Do(N,M,S);
}


int main()
{
    int n,m,s;
    fin>>t;
    for(int i=1; i<=t; ++i)
    {
        fin>>n>>m>>s;
        Read(n,m,s);
    }
    return 0;
}