#include <fstream>
#define MAX 50010
#define infinit 100000000

using namespace std;

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

struct nod
{
    int inf,cost;
    nod *next;
};

typedef struct nod nod;
nod * sir[MAX];

int n,m,vi;
int d[MAX],viz[MAX],T[MAX],sip[MAX];

void adauga(int a,int b,int c)
{
    nod *q=new nod;
    q->inf=a;
    q->cost=c;
    q->next=sir[b];
    sir[b]=q;
}

void citire()
{
    fin>>n>>m>>vi;
    for (int i=1;i<=n;i++)
    {
            fin>>sip[i];
            sir[i]=NULL;
    }

    int a,b,c;
    for (int i=0;i<m;i++)
    {
        fin>>a>>b>>c;
        adauga(a,b,c);
        adauga(b,a,c);
    }
}
void prima_faza()
{
    for (nod *r=sir[vi];r;r=r->next)
                    if (d[r->inf]==infinit||(d[r->inf]>d[vi]+r->cost))
                    {
                        d[r->inf]=d[vi]+r->cost;
                        T[r->inf]=vi;
                        }
}

void dijkstra()
{
    memset(T,0,sizeof(T));
    memset(viz,0,sizeof(viz));
    for (int i=0;i<=n;i++)
        d[i]=infinit;
    d[vi]=0;
    viz[vi]=1;
    T[vi]=0;
    prima_faza();
    int poz,min;
for (int p=1;p<=n;p++)
{
    min=infinit;
        for (int i=1;i<=n;i++)
              if (viz[i]==0 && d[i]<min)
              {     min=d[i];
                    poz=i;
              }
              if (min==infinit)
                return ;
        viz[poz]=1;
                for (nod *r=sir[poz];r;r=r->next)
                    if (d[r->inf]==infinit||(d[r->inf]>d[poz]+r->cost))
                    {
                        d[r->inf]=d[poz]+r->cost;
                        T[r->inf]=poz;

                    }
    }
}

void afisare()
{
    int ok=0;
    for (int i=1;i<=n;i++)
        if (d[i]==infinit)
        {
                if (sip[i]!=0)
            {
                    ok=1;
                break;
            }
        }
        else
            if (sip[i]!=d[i])
            {
                    ok=1;
                break;
            }
        if (ok)
            fout<<"NU";
        else
            fout <<"DA";
    fout<<"\n";
}

int main()
{
    int t=0;
    fin>>t;
    while(t)
    {
        citire();
        dijkstra();
        afisare();
        t--;
    }
    return 0;
}