#include <iostream>
#include <fstream>
#define pinf 100000
using namespace std;
ifstream fin("distante.in");
ofstream fout("distante.out");
int N,M,D[50010],viz[50010],rez[50010];
struct nod
{
    int info,cost;
    nod* urm;
};
nod *L[50010];
void init(int S)
{
    int i;
    for(i=1; i<=N; i++)
    {
        D[i]=pinf;
        viz[i]=0;
    }
    D[S]=0;
}
void citire()
{
    int i,x,y,c;
    nod *p;
    for(i=1; i<=M; i++)
    {
        fin>>x>>y>>c;
        p=new nod;
        p->urm=L[x];
        p->info=y;
        p->cost=c;
        L[x]=p;

    }
}
void djikstra()
{
    int i,j,poz,minn=0;
    nod *p;
    while(minn!=pinf)
    {
        minn=pinf;
        for(j=1; j<=N; j++)
        {
            if(viz[j]==0)
            {
                if(D[j]<minn)
                {
                    poz=j;
                    minn=D[j];
                }
            }
        }
        if(minn!=pinf)
        {
            viz[poz]=1;
            p=L[poz];
            while(p!=NULL)
            {
                if(D[p->info]>D[poz]+p->cost)
                {
                    D[p->info]=D[poz]+p->cost;
                }
                p=p->urm;
            }
        }
    }
}
void comparare(int S)
{
    int i,ok=1;
    for(i=1; i<=N; i++)
    {
          if(D[i]!=rez[i])
            ok=0;
    }
    if(ok==1)
        fout<<"DA\n";
    else
        fout<<"NU\n";

}
void stergere()
{
    int i;
    nod *p;
    for(i=1;i<=N;i++)
    {
        p=L[i];
        while(L[i]!=NULL)
        {
            L[i]=L[i]->urm;
            delete p;
            p=L[i];
        }
    }
}
int main()
{
    int i,S,k,T;
    nod *p;
    fin>>T;
    for(k=1; k<=T; k++)
    {
        fin>>N>>M>>S;
        for(i=1;i<=N;i++)
            fin>>rez[i];
        citire();
        init(S);
        p=L[S];
        while(p!=NULL)
        {
            D[p->info]=p->cost;
            p=p->urm;
        }
        viz[S]=1;
        djikstra();
        comparare(S);
        stergere();
    }
}