#include <fstream>
#include <vector>
#define nmax 50001
#define INF 1<<30

using namespace std;

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

int t,n,s,m,heap[nmax],cost[nmax],poz[nmax],cmp[nmax];
bool ok;

vector < pair < int , int > >leg[nmax];

inline int father(int k)
{
    return k/2;
}

inline int leftson(int k)
{
    return k*2;
}

inline int rightson(int k)
{
    return k*2+1;
}

void sift(int n, int k)
{
    int son;
    do
    {
        son=0;
        if(leftson(k)<=n)
        {
            son=leftson(k);
            if(rightson(k)<=n && cost[heap[leftson(k)]]>cost[heap[rightson(k)]])
                son=rightson(k);
            if(cost[heap[son]]>=cost[heap[k]])
                son=0;
        }

        if(son)
        {
            swap(heap[k], heap[son]);
            swap(poz[heap[k]],poz[heap[son]]);
            k=son;
        }
    }
    while(son);
}

void percolate(int n, int k)
{
    int key=heap[k];
    while(k>1 && cost[key]<cost[heap[father(k)]])
    {
        heap[k]=heap[father(k)];
        poz[heap[k]]=k;
        k=father(k);
    }

    heap[k]=key;
    poz[heap[k]]=k;
}

inline void read()
{
    int i,a,b,c,z=1;

    fin>>n>>m>>s;

    for(i=1;i<=n;i++)
        fin>>cmp[i];

    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        leg[a].push_back(make_pair(b,c));
        leg[b].push_back(make_pair(a,c));
    }

    heap[1]=s;
    poz[s]=1;
    cost[s]=0;

    for(i=1;i<=n;i++)
    {
        if(i!=s)
        {
            heap[++z]=i;
            poz[i]=z;
            cost[i]=INF;
        }
    }
}

void delete_elem(int &n, int k)
{
    heap[k]=heap[n];
    poz[heap[k]]=k;
    n--;
    if(k>1 && heap[k]<heap[father(k)])
        percolate(n,k);
    else
        sift(n,k);
}

inline void solve()
{
    int z=n,i,node,a,b;
    while(z)
    {
        node=heap[1];
        delete_elem(z,1);
        for(i=0;i<leg[node].size();i++)
        {
            a=leg[node][i].first;
            b=leg[node][i].second;
            cost[a]=min(cost[a],cost[node]+b);
            if(poz[a]>1 && cost[a]<cost[heap[father(poz[a])]])
                percolate(z,poz[a]);
            else
                sift(z,poz[a]);
        }
    }
}

inline void clearr()
{
    ok=true;
    for(int i=1;i<=n;i++)
        leg[i].erase(leg[i].begin(),leg[i].end());
}

inline void write()
{
    for(int i=1;i<=n;i++)
        {
            if(cmp[i]!=cost[i])
            {
                ok=false;
                break;
            }
        }
    if(ok==true)
        fout<<"DA\n";
    else
        fout<<"NU\n";
}

int main()
{
    fin>>t;
    for(int i=1;i<=t;i++)
    {
        clearr();
        read();
        solve();
        write();
    }

    return 0;
}