#include <fstream>

using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
typedef int ll;
struct nod
{
    int val;
    ll cost;
    nod *urm;
};
typedef nod *pnod;
#define nmax 50003
#define inf 2000000000
pnod v[nmax],p;
void ad(int x,int y,ll c)
{
    p=new nod;
    p->val=y;
    p->cost=c;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
int k,minim,n,m,father;
ll dist[nmax];
int h[nmax],poz[nmax];
ll newdist[nmax];
void upheap(int son)
{
    while(son>1)
    {
        father=son>>1;
        if(dist[h[father]]>dist[h[son]])
        {
            swap(h[father],h[son]);
            swap(poz[h[father]],poz[h[son]]);
            son=father;
        }
        else
            son=1;
    }
}
int son;
void downheap(int father)
{
    son=1;
    while(son)
    {
        son=0;
        if((father<<1)<=k)
        {
        son=(father<<1);
        if(son+1<=k)
            if(dist[h[son+1]]<dist[h[son]])
                    son+=1;
        if(dist[h[father]]>dist[h[son]])
        {
            swap(poz[h[father]],poz[h[son]]);
            swap(h[father],h[son]);
            father=son;
        }
        else
            son=0;
        }
    }
}
int main()
{
    int i,x,y;
    ll c;
    int t,rad;
    f>>t;
    for(int q=1;q<=t;q++)
    {
    f>>n>>m>>rad;
    for(i=1;i<=n;i++)
    {
        f>>newdist[i];
        v[i]=new nod;
        v[i]->urm=0;
        dist[i]=inf;
        poz[i]=-1;
    }
    dist[0]=inf;
    poz[0]=-1;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        ad(x,y,c);
        ad(y,x,c);
    }
    k=1;
    h[1]=rad;
    poz[rad]=1;
    dist[rad]=0;
    while(k)
    {
        minim=h[1];
        swap(h[1],h[k]);
        poz[h[1]]=1;
        k-=1;
        downheap(1);
        p=v[minim]->urm;
        while(p)
        {
            if(dist[p->val]>dist[minim]+p->cost)
            {
                dist[p->val]=dist[minim]+p->cost;
                if(poz[p->val]==-1)
                {
                    k+=1;
                    h[k]=p->val;
                    poz[p->val]=k;
                    upheap(k);
                }
                else
                    upheap(poz[p->val]);
            }
            p=p->urm;
        }
    }
    i=1;
    while(i<=n and dist[i]==newdist[i])
        i+=1;
    if(i==n+1)
        g<<"DA";
    else
        g<<"NU";
    g<<'\n';
    }
    return 0;
}