#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
int n,i,nrt,m,sursa,ver[50005],dist[50005],nod,vecin,cost,val,x,y,z,ok;
vector<pair<int, int> >v[50005];
struct andreea
{
    int value,node;
}aint[200005];
void build(int nod, int st, int dr)
{
    int mij;
    if(st==dr)
    {
        aint[nod].node=st;
        aint[nod].value=dist[st];
        return;
    }
    mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    if(aint[nod*2].value<aint[nod*2+1].value)
    {
        aint[nod].value=aint[nod*2].value;
        aint[nod].node=aint[nod*2].node;
    }
    else
    {
        aint[nod].value=aint[nod*2+1].value;
        aint[nod].node=aint[nod*2+1].node;
    }
}
void update(int nod, int st, int dr, int poz, int val)
{
    int mij;
    if(st==dr)
    {
        aint[nod].node=st;
        aint[nod].value=val;
        return;
    }
    mij=(st+dr)/2;
    if(poz<=mij)update(nod*2,st,mij,poz,val);
    else update(nod*2+1,mij+1,dr,poz,val);
    if(aint[nod*2].value<aint[nod*2+1].value)
    {
        aint[nod].value=aint[nod*2].value;
        aint[nod].node=aint[nod*2].node;
    }
    else
    {
        aint[nod].value=aint[nod*2+1].value;
        aint[nod].node=aint[nod*2+1].node;
    }
}
int main()
{
    freopen("distante.in","r",stdin);
    freopen("distante.out","w",stdout);
    scanf("%d",&nrt);
    while(nrt)
    {
        nrt--;
        scanf("%d%d%d",&n,&m,&sursa);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&ver[i]);
            v[i].clear();
        }

        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            v[x].push_back(make_pair(y,z));
            v[y].push_back(make_pair(x,z));
        }
        for(i=1;i<=n;i++)
            dist[i]=INF;
        dist[sursa]=0;
        build(1,1,n);
        while(aint[1].value!=INF)
        {
            nod=aint[1].node; val=aint[1].value;
            for(i=0;i<v[nod].size();i++)
            {
                vecin=v[nod][i].first;
                cost=v[nod][i].second;
                if(cost+val<dist[vecin])
                {
                    dist[vecin]=cost+val;
                    update(1,1,n,vecin,cost+val);
                }
            }
            x=nod;
            y=INF;
            update(1,1,n,x,y);
        }
        ok=1;
        for(i=1;i<=n;i++)
            if(dist[i]!=ver[i])ok=0;
            if(ok==1)printf("DA\n");
            else printf("NU\n");
    }
    return 0;
}