#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

#define infinity 0x3f3f3f3f

const int sz = (int)5e4+1;

FILE *in,*out;

bool wrong;
int num, dist[sz], finalDist[sz];
vector<pair<int, int> > graph[sz];

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;

int main()
{
    in=fopen("distante.in","rt");
    out=fopen("distante.out","wt");

    fscanf(in,"%d",&num);
    while(num--)
    {
        int rFrom, rTo, rCost, nodes, edges, source;
        fscanf(in,"%d%d%d",&nodes, &edges, &source);

        for(int i=1; i<=nodes; ++i)
            fscanf(in,"%d",&dist[i]);
        for(int i=1; i<=edges; ++i)
        {
            fscanf(in,"%d%d%d",&rFrom, &rTo, &rCost);
            graph[rFrom].push_back(make_pair(rCost, rTo));
            graph[rTo].push_back(make_pair(rFrom, rCost));
        }

        memset(finalDist, infinity, sizeof(finalDist));
        heap.push(make_pair(0, source));
        finalDist[source] = 0;

        while(!heap.empty())
        {
            int current = heap.top().second;
            heap.pop();

            vector <pair<int, int> >::iterator it, end = graph[current].end();
            for(it=graph[current].begin(); it!=end; ++it)
            {
                if(finalDist[current] + it->first < finalDist[it->second])
                {
                    finalDist[it->second] = finalDist[current] + it->first;
                    heap.push(make_pair(finalDist[it->second], it->second));
                }
            }
        }
        for(int i=1; i<=nodes; ++i)
        {
            if(dist[i] != finalDist[i])
            {
                fprintf(out, "NU\n");
                wrong = true;
                break;
            }
        }
        if(!wrong)
            fprintf(out,"DA\n");

        for(int i=0; i<nodes; ++i)
            graph[i].clear();
        memset(dist, 0, sizeof(dist));
    }

    fclose(in);
    fclose(out);
    return 0;
}