#include<bits/stdc++.h>
using namespace std;

ifstream in("distante.in");
ofstream g("distante.out");

const int NMAX = 50001;
const int oo = 1 << 30;
typedef pair<int, int> Edge;

int T, START, N, M;
int Solution2[NMAX];

vector<int>Solution;
vector<Edge>myList[NMAX];
multiset<Edge>myHeap;

void Read()
{
    in>>N>>M>>START;
    for(int i = 1; i <= N; i++) in>>Solution2[i];
    for(int x, y, cost, i =  1; i <= M; ++i )
    {
        in >> x >> y >> cost;
        myList[x].push_back(make_pair(y, cost));
    }
}

void Initialize()
{
    Solution.resize(N+1);
    for(int i = 2; i <= N; i++)
    {
        Solution[i] = oo;
    }
    myHeap.insert(make_pair(0, START));

}

void Dijkstra()
{
    vector<Edge>::iterator it;
    while(!myHeap.empty())
    {
        Edge node = *myHeap.begin();
        myHeap.erase( myHeap.begin() );

        for(it = myList[node.second].begin(); it != myList[node.second].end(); ++it )
        {
            if(Solution[it->first] > it->second + node.first)
            {
                myHeap.erase( make_pair(Solution[it->first], it->first));
                Solution[it->first] = it->second + node.first;
                myHeap.insert( make_pair(Solution[it->first], it->first) );
            }
        }
    }
}

void Clear()
{
    Solution.clear();
    myHeap.clear();
    myList[NMAX].clear();
}

int Drum()
{
    for(int i = 1; i <= N; i++)
        if(Solution[i] != Solution2[i]) return 0;
    return 1;
}

void Main_Function()
{
    Read();
    Initialize();
    Dijkstra();
    if(Drum()) g<<"DA"<<"\n";
    else g<<"NU";
    Clear();
}

int main(){
    in>>T;
    for(int i = 1; i <= T; i++)
    {
        Main_Function();
    }

    return 0;
}