#include <cstdio> 
#include <cstring>
#include <cstdlib>

using namespace std;

#define FIN "distante.in"
#define FOUT "distante.out"
#define MAX_N 50005
#define INF 0x3f3f3f3  
  
  
int N, M, i, k;   
int *A[MAX_N];   
int *C[MAX_N];

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 readdata ( void ) 
    {
        // construim graful + graful transpus 
        int i, c, x ,y;
        scanf ("%d %d %d", &N, &M, &S);
        for (i = 1; i <= N; ++i)
             scanf ("%d", Dist + i);
  
        for (i = 1; i <= N; ++i) A[i][0] = 0;           
        for (i = 1; i <= M; ++i)
        {
            scanf ("%d %d %d", &x, &y, &c);
            ++A[x][0];
            ++C[x][0];
            A[x] = (int *) realloc (A[x], (A[x][0] + 1)*sizeof(int));
            C[x] = (int *) realloc (C[x], (C[x][0] + 1)*sizeof(int));
            A[x][A[x][0]] = y;
            C[x][C[x][0]] = c;
        }
    }


    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 (j = 1; j <= A[i][0]; ++j)
                 if (Dist[i] + C[i][j] < Dist[A[i][j]]) ok = 0;
         
         for (i = 1; i <= N; ++i)
             for (j = 1; j <= A[i][0]; ++j)
               if (A[i][j] != S)  
                 if (Dist[A[i][j]] == Dist[i] + C[i][j]) P[A[i][j]] = 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);
         for (i = 1; i <= MAX_N - 5; ++i)
         { 
            A[i] = (int *) realloc (A[i], sizeof(int)), A[i][0] = 0;
            C[i] = (int *) realloc (C[i], sizeof(int)), C[i][0] = 0;
         }

         while (T)
         {
               readdata();   
               solve();   
               --T;
         }
  
               return 0;   
    }