#include <stdio.h>
#include <malloc.h>
int t, n, m, s, *dist, *d, *p;
FILE *f, *g;

struct muchie
{
       int a;
       int b;
       int c;
};
typedef struct muchie* Muchie;

struct nod
{
       struct muchie data;
       struct nod* next;
};


struct coada
{
       int size;
       struct nod* prim;
       struct nod* ultim;
};
typedef struct coada* Coada;
Coada Q;

Coada Q_New()
{
      Coada Q=(Coada)malloc(sizeof(struct coada));
      Q->size=0;
      Q->prim=Q->ultim=0;
      return Q;      
}

struct muchie M_New()
{
       struct muchie m;
       m.a=0;
       m.b=0;
       m.c=0;
       return m;
}

void Enq(Coada Q, struct muchie x)
{
     struct nod* nou = (struct nod*) malloc (sizeof(struct nod));
     nou->data = x;
     nou->next = 0;
     if (Q->size==0)
     {
        Q->prim=nou;         
        Q->ultim=nou;         
     }
     else
     {
         Q->ultim->next=nou;
         Q->ultim=nou;
         Q->ultim->next=0;
     }
     //printf("bag in coada\n");
     Q->size++;
}

struct muchie Deq(Coada Q)
{
    if (Q->size==0)
       return M_New();
    struct muchie x=Q->prim->data;
    struct nod* sters=Q->prim;
    Q->prim=Q->prim->next;
    if (Q->prim==0)
       Q->ultim=0;
    free(sters);
    Q->size--;
    return x;
}

int bellmanFord(int n, int *dist)
{    
     int i,j,k;
     struct muchie x;
     d=(int*) malloc ((n+1) *sizeof(int));
     p=(int*) malloc ((n+1) *sizeof(int));     
     /*for each v in V[G]

     3         d[v]= ?;

     4.         p[v]=null;

     5 d[s]=0;

     6 p[s] = null;

     7 for i = 1 to |V|                                                // de |V| ori

     8         for each (u,v) in E[G]                           // pentru fiecare muchie (u,v)

     9                     if d[v]>d[u]+w(u,v)                   // relaxeaza( (u,v)

     10                               d[v]=d[u]+w(u,v);

     11                               p[v]=u;        */
     
     for (i=1; i<=n; i++)
     {
         d[i]=1000;
         p[i]=-1;
     }
     d[s]=0;
     p[s]=-1;
     for (i=1; i<=n; i++)
     {
         struct nod* parcurg = (struct nod*) malloc (sizeof(struct nod));
         parcurg=Q->prim;
         while (parcurg!=NULL)
         {
               //printf("%d %d %d\n", parcurg->data.a, parcurg->data.b, parcurg->data.c);
               if (d[parcurg->data.b]>d[parcurg->data.a]+parcurg->data.c)
               {
                  d[parcurg->data.b]=d[parcurg->data.a]+parcurg->data.c;   
                  //printf("b = %d si d devine = %d\n", parcurg->data.b, d[parcurg->data.b]);
                  p[parcurg->data.b]=parcurg->data.a;
               }
               parcurg=parcurg->next;
         }
         //printf("Q->size=%d\n", Q->size); 
     }
     for (i=1; i<=n; i++)
         if (dist[i-1]!=d[i]) return 0;
     return 1;
}

int main()
{
    int i, j, k, a, b, c;
    struct muchie x;
    dist=(int*) malloc (n *sizeof(int));
    f=fopen("distante.in", "r");
    g=fopen("distante.out", "w");    
    fscanf(f, "%d\n", &t);
    //printf("%d\n", t);
    for (i=0; i<t; i++)
    {
        Q=Q_New();
        fscanf(f, "%d %d %d", &n, &m, &s);
        //printf("%d %d %d\n", n,m,s);
        for (k=0; k<n; k++)
        {
            fscanf(f, "%d ", &dist[k]);            
            //printf("%d ", dist[k]);
        }
        //printf("\n");
        for (j=0; j<m; j++)
        {
            fscanf(f, "%d %d %d\n", &a, &b, &c);
//            printf("%d %d %d\n", a, b, c);
            x.a=a;
            x.b=b;
            x.c=c;
            Enq(Q, x);
            //printf("%d %d %d\n", x.a, x.b, x.c);
            //printf("size=%d\n", Q->size);
        }
        //printf("\n");
        //printf("size=%d\n", Q->size);
       /* while (Q->size>0)
        {
              x=Deq(Q);
              printf("%d %d %d\n", x.a, x.b, x.c);
        }*/
        if (bellmanFord(n, dist)) fprintf(g, "DA\n");
        else fprintf(g, "NU\n");
    }
    return 0;
}