#include<fstream>
#include<string.h>
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int n,m,T[50007],H[50007],D[50007],t,source,P[50007],nh;
bool U[50001];
struct lista{int nod,c; lista *leg;} *G[50007];
void adaug(int i,int j,int cost)
{
    lista *p;
    p=new lista;
    p->nod=j;
    p->leg=G[i];
    p->c=cost;
    G[i]=p;
}
void citire()
{
    f>>n>>m>>source;
    for(int i=1;i<=n;++i) f>>D[i];
    int i,j,cost;
    while(m--)
    {
        f>>i>>j>>cost;
        adaug(i,j,cost);
        adaug(j,i,cost);
    }
}
void swp(int i,int j)
{
    int aux;
    aux=H[i];
    H[i]=H[j];
    H[j]=aux;
    P[H[i]]=i; P[H[j]]=j;
}
void HeapDw(int i,int k)
{
    int St=0,Dr=0,t=0;
    if(2*i+1<=k)
    {
        St=2*i+1;
        if(2*i+2<=k) Dr=2*i+2;
        else Dr=St+1;
    }
	if(St==Dr&&St==0) return;
        if(St>Dr) t=2*i+1;
        else 
	{ if(D[H[St]]<D[H[dr]]) t=2*i+1;
	  else  t=2*i+2;
	}
        if(D[H[t]]<D[H[i]])
        {
            swp(i,t);
            HeapDw(t,k);
        }
    }
}
int scoate()
{
    swp(0,nh-1);
    P[H[nh-1]]=0; nh--;
    HeapDw(0,nh-1);
    return H[nh];
}
void HeapUp(int i)
{
    if(i<=0) return;
    int t=(i-1)/2;
    if(D[H[t]]>D[H[i]])
    {
        swp(i,t);
        HeapUp(t);
    }
}
void BuildHp()
{
    for(int i=0;i<nh;++i) HeapUp(i);
}
void dij(int start)
{
    int nod; lista *p;
    memset(T,0,sizeof T);
    memset(U,0,sizeof U);
    for(int i=0;i<n;++i) H[i]=i+1,P[i+1]=i;
    BuildHp();  nh=n; int ok=1;
    while(nh>0&&ok)
    {
        nod=scoate();
        for(p=G[nod];p&&ok;p=p->leg)
            if(D[p->nod]>D[nod]+p->c)
            { ok=0;
              break;
            }
    }
    if(ok) g<<"DA"<<'\n';
    else g<<"NU"<<'\n';
}
int main()
{
    f>>t;
    for(int test=1;test<=t;++test)
    {
        citire();
        dij(source);
    }
}