//Acest program a fost facut la ora 11:32
//este bellama-FORD fara STL
#include <cstdio>
#include <fstream>
#define inff 0x3f3f3f
#define MAX_N 100001

using namespace std;

struct nod
{
    int dest, cost;
    nod * next;
}*V[MAX_N],*U[MAX_N];


struct nodd
{
    int inf;
    nodd* next;
}*Q,*U2;


char viz[MAX_N];
int N,M,D[MAX_N],lol,nr,ok[MAX_N];

void baga(nod *&u,nod *&V,int poz,int c)
{
    nod *nou=new nod;
    nou->dest=poz;
    nou->cost=c;
    nou->next=NULL;
    if (!V)
        V=nou;
    else
        u->next=nou;
    u=nou;

}


void stergere(nodd *&p)
{
    nodd *x=p;
    p=p->next;
    delete x;
}


void baga2(nodd *&u,nodd *&V,int poz)
{
    nodd *nou=new nodd;
    nou->inf=poz;
    nou->next=NULL;
    if (!V)
        V=nou;
    else
        u->next=nou;
    u=nou;

}

void citire()
{
    int x,y,z;
    scanf("%d %d %d",&N,&M,&lol);
    for(int i=1;i<=N;i++)
        scanf("%d",&ok[i]);
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d %d %d",&x,&y,&z);
        baga(U[x],V[x],y,z);
    }
}

void solve()
{
    memset(D, inff, sizeof D);
    memset(viz,'0', sizeof viz);

    baga2(Q,U2,lol);
    D[lol] = 0;
    viz[lol] ='1';
    while(Q)
    {
        int noddd = Q->inf;
        stergere(Q);
        viz[noddd]='0';
        for(nod *p=V[noddd];p;p=p->next)
            if(D[p->dest]>D[noddd]+p->cost)
            {
                D[p->dest]=D[noddd]+p->cost;
                if(viz[p->dest]!='1')
                {
                    baga2(U2,Q,p->dest);
                    viz[p->dest]='1';
                }
            }
    }
}
void afisare()
{
    for(int i = 1; i <= N; ++i){
      //  printf("%d ",ok[i]);
        if (i!=lol)
            if(D[i]!=ok[i]){
                printf("NU");
                 printf("\n");
                return;
            }
    }
    printf("DA");
    printf("\n");
}

int main()
{
    freopen ("distante.in","r",stdin);
    freopen ("distante.out","w",stdout);
    scanf("%d",&nr);
    for(int i=0;i<nr;i++){
        citire();
        V[MAX_N]=NULL;
        U[MAX_N]=NULL;
        Q=NULL;
        U2=NULL;
        solve();
        afisare();
    }
    return 0;
}