#include <cstdio> 
#include <cstring>

using namespace std;

#define FIN "distante.in"
#define FOUT "distante.out"
#define MAX_N 50005
#define INF 0x3f3f3f3  
  
typedef struct NOD   
{   
    int nod, cost;   
    NOD *next;   
};   
  
int N, M, i, k;   
NOD *A[MAX_N];   

int D[MAX_N]; // distante
int H[MAX_N]; // heap
int P[MAX_N];   
int S;
int Dist[MAX_N];
int T;
  
    void readdata()   
    {   
         int x, y, c, i;
    
         for (i = 1; i <= N; ++i)
         {
             for (NOD *p = A[i]; p != NULL; p = p->next)
                 delete (p);
         }
         for (i = 1; i <= N; ++i) A[i] = new (NOD), A[i] = NULL; 
         scanf("%d %d %d", &N, &M, &S);   
         for (i = 1; i <= N; ++i)
             scanf ("%d", Dist + i);
         for (i = 1; i <= M; ++i)   
         {   
             scanf("%d %d %d", &x, &y, &c);   
             NOD *q = new (NOD);
             q->nod = y;
             q->cost = c;
             q->next = A[x];
             A[x] = q;
         }   
         /*
         for (i = 1; i <= N; ++i)
         {
             for (NOD *p = A[i]; p != NULL; p = p->next)
                 printf ("%d ", p->nod);
             printf ("\n");
         }
         */
                 
    }   

    void solve ()
    {
         if (Dist[S] != 0) 
         {
            printf ("NU\n");
            return;
         }
         memset (P, 0, sizeof (P));
         
         int i, j, ok = 1;
         for (i = 1; i <= N; ++i)
             for (NOD *p = A[i]; p != NULL; p = p->next)
                 if (Dist[i] + p->cost < Dist[p->nod]) ok = 0;
         
         for (i = 1; i <= N; ++i)
             for (NOD *p = A[i]; p != NULL; p = p->next)
               if (p->nod != S)  
                 if (Dist[p->nod] == Dist[i] + p->cost) P[p->nod] = 1;
         for (i = 1; i <= N; ++i)
             if (!P[i] && i!=S) ok = 0;
         if (ok) printf ("DA\n"); else printf ("NU\n");
    }  
  
    int main()   
    {   
         freopen (FIN, "r", stdin);
         freopen (FOUT, "w", stdout);
    
         scanf ("%d", &T);
         while (T--)
         {
               readdata();   
               solve();   
         }
  
               return 0;   
    }