#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
const int OO= (1<<30);
const int NMAX= 5e4+2;
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int N,M,nodStart;
int D [NMAX], distanteAflate[NMAX];
vector < pair <int, int> > G[NMAX];
bool inCoada [NMAX];

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

priority_queue <int, vector <int>, compara > q;

void citire()
{
    for (int i=1; i<=N; i++)
        f>>distanteAflate[i];
    for (int i=1; i<=M; i++)
    {
        int sursa, destinatie, cost;
        f>>sursa>>destinatie>>cost;
        G[sursa].push_back(make_pair(destinatie, cost));
    }
}

void afisare()
{
    bool ok=1;
    for (int i =1; i<=N; i++)
        if (distanteAflate[i]!=D[i])
        {
            ok=0;
            break;
        }
    if (ok)
        g<<"DA"<<"\n"; else
        g<<"NU"<<"\n";
}

void dijkstra()
{
    for (int i=1; i<=N; i++)
         {
             D[i]=OO;
             inCoada[i]=false;
         }
    D[nodStart]=0;
    q.push(nodStart);
    inCoada[nodStart]=true;
    while (!q.empty())
    {
        int nodCurent;
        nodCurent=q.top();
        q.pop();
        inCoada[nodCurent]=false;
        for (int i=0; i<G[nodCurent].size(); i++)
        {
            int next, cost;
            next=G[nodCurent][i].first;
            cost=G[nodCurent][i].second;
            if (D[next]>D[nodCurent]+cost)
            {
                D[next]=D[nodCurent]+cost;
                if (inCoada[next]==false)
                {
                    inCoada[next]=true;
                    q.push(next);
                }
            }

        }

    }
}


int main()
{
    int nrGrafuri;
    f>>nrGrafuri;
    for (int i=1; i<=nrGrafuri; i++)
    {
        f>>N>>M>>nodStart;
        citire();
        dijkstra();
        afisare();
        fill_n(G, N, vector<pair<int, int> >());
    }
    return 0;
}