#include <bits/stdc++.h>

using namespace std;


const int MAX = 50001;

int Distance[MAX];
int compareDistance[MAX];
bitset < MAX > beenThere;

vector < pair < int , int > > myVector[MAX];

struct compare
{
    bool operator()(int x , int y)
    {
        return Distance[x] > Distance[y];
    }
};

int graphNumber, numberOfNodes , numberOfEdges , startingNode;

priority_queue < int  , vector < int > , compare > myQueue;

inline void Read()
{
    scanf("%d%d%d", &numberOfNodes , &numberOfEdges , &startingNode);

    for ( int i = 1; i <= numberOfNodes ; ++i)
    {
        int x;
        scanf("%d" , &x);

        compareDistance[i] = x;
    }

    for ( int i = 1; i <= numberOfEdges ; ++i)
    {
        int x,y,price;

        scanf("%d%d%d" , &x ,&y , &price);

        myVector[x].push_back(make_pair(y,price));
        myVector[y].push_back(make_pair(x,price));
    }


}

inline void Reset()
{
    for ( int i = 1; i <= numberOfNodes ; ++i)
    {
        Distance[i] = 100000;
        myVector[i].clear();
    }
}

void Dijkstra( int Node)
{

    for ( int i = 1 ; i <= numberOfNodes ; ++i)
        Distance[i] = (1 << 30);
    beenThere[Node] = true;
    Distance[Node] = 0;

    myQueue.push(Node);

    while(!myQueue.empty())
    {
        int currentNode = myQueue.top();
        myQueue.pop();

        beenThere[currentNode] = false;

        for ( size_t k = 0 ; k < myVector[currentNode].size() ; ++k)
        {
            int neighbor = myVector[currentNode][k].first;
            int price = myVector[currentNode][k].second;

            if(Distance[currentNode] + price < Distance[neighbor])
            {
                Distance[neighbor] = Distance[currentNode] + price;

                if(beenThere[neighbor] == false)
                {
                    myQueue.push(neighbor);
                    beenThere[neighbor] = true;
                }
            }
        }
    }
}

int main()
{
      freopen("distante.in" , "r" , stdin);
      freopen("distante.out" , "w"  ,stdout);

      scanf("%d" , &graphNumber);

       for ( int i = 1; i <= graphNumber ; ++i)
      {
          Read();
          Dijkstra(startingNode);

          bool OK = true;

          for ( int j = 1; j <= numberOfNodes ; ++j)
          {
              myVector[j].clear();

              if(compareDistance[j] != Distance[j])
                OK = false;
          }

          if(OK == true)
            printf("DA\n");
          else printf("NU\n");


      }




}