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

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

struct ed
{
    int e,c;
    ed(int e=0,int c=0)
    {
        this->e=e;
        this->c=c;
    }
};

vector<ed> adj[nmax]; //de ref
int n,m,s;
int h[nmax],k;
int poz[nmax];
int dij[nmax],val[nmax];

int v[nmax];


void swp(int a, int b)
{
    poz[h[a]]=b;
    poz[h[b]]=a;
    int aux=h[a];
    h[a]=h[b];
    h[b]=aux;
}

void upheap(int nod)
{
    if(nod==1) return;
    if(val[h[nod]]<val[h[nod/2]])
    {
        swp(nod,nod/2);
        upheap(nod/2);
    }
}

void downheap(int nod)
{
    if(nod*2+1<=k)
    {
        int nr=(val[h[nod*2+1]]<val[h[nod*2]]?nod*2+1:nod*2);
        if(val[h[nod]]>val[h[nr]])
        {
            swp(nod,nr);
            downheap(nr);
        }
    }
    else if(nod*2<=k&&val[h[nod]]>val[h[nod*2]])
        swp(nod,nod*2);
}




void dk(int st)
{
    k=0;
    for(int i=1;i<=n;i++)
    {
        val[i]=INT_MAX;
        poz[i]=-1;
        dij[i]=INT_MAX;
    }
    k++;
    val[st]=0;
    poz[st]=1;
    h[1]=st;
    while(val[h[1]]!=INT_MAX)
    {
        //cout<<"here"<<' '<<arb[1]<<'\n';
        int c=h[1];
        dij[c]=val[c];
        val[c]=INT_MAX;
        downheap(1);
        for(auto e:adj[c])
        {
            if(dij[e.e]==INT_MAX&&val[e.e]>dij[c]+e.c)
            {
                if(poz[e.e]==-1)
                {
                    k++;
                    poz[e.e]=k;
                    h[k]=e.e;
                }
                val[e.e]=dij[c]+e.c;
                upheap(poz[e.e]);
            }
        }
    }
}


int main()
{
    //FILE* f= fopen("distante.in","r");
    //FILE* g= fopen("distante.out","w");


    int t; f>>t;
    while(t--)
    {
        f>>n>>m>>s;
        //fscanf(f,"%i %i %i",&n, &m, &s);
        for(int i=1;i<=n;i++)
        {
            adj[i].clear();
            //fscanf(f,"%i",&v[i]);
            f>>v[i];
        }
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            //fscanf(f,"%i %i %i",&a,&b,&c);
            f>>a>>b>>c;
            adj[a].push_back(ed(b,c));
            adj[b].push_back(ed(a,c));
        }
        dk(s);
        bool ok=1;
        for(int i=1;i<=n;i++)
        {
            if(v[i]!=dij[i]) ok=0;
        }
        if(ok) g<<"DA\n";
        else g<<"NU\n";
    }
    //f.close();
    //g.close();
    return 0;
}