#include<stdio.h>
#include<stdlib.h>
#define dim 50001

int *a[dim], *c[dim];

int d[dim];

int T, N, M, X0;

int main()
{
    int i, j, ok, x, y, cost, k;
    
    freopen("distante.in", "r", stdin);
    freopen("distante.out", "w", stdout);
    
    scanf("%d", &T);
    
    while(T)
    {
            scanf("%d %d %d", &N, &M, &X0);
            
            ok=1;
            
            for(i = 1; i <= N; i++)
            {
                  scanf("%d", &d[i]);
                  
                  a[i] = (int *)realloc(a[i], sizeof(int));
                  c[i] = (int *)realloc(a[i], sizeof(int));
                  
                  a[i][0] = 0;
                  c[i][0] = 0;                 
            }
            
            for(j = 1; j <= M; j++)
            {
                  scanf("%d %d %d", &x, &y, &cost);
                  
                  //x
                  a[x][0]++;
                  a[x] = (int *)realloc(a[x], ( a[x][0] + 1 ) * sizeof(int));
                  a[x][a[x][0]] = y;
                  
                  c[x][0]++;
                  c[x] = (int *)realloc(c[x], ( c[x][0] + 1 ) * sizeof(int));
                  c[x][c[x][0]] = cost;
                  
                  //y
                  a[y][0]++;
                  a[y] = (int *)realloc(a[y], ( a[y][0] + 1 ) * sizeof(int));
                  a[y][a[y][0]] = x;
                  
                  c[y][0]++;
                  c[y] = (int *)realloc(c[y], ( c[y][0] + 1 ) * sizeof(int));
                  c[y][c[y][0]] = cost;
                  
                  if( ( d[x] + cost ) < d[y] ) ok = 0;
                  
            }
            
            if( d[X0] != 0 ) ok=0;
                else if( ok )
                {
                    for(i = 1; i <= N; i++)
                    {
                          //caut d[i]
                          k=0;
                          for(j = 1; j <= a[i][0]; j++)
                          {
                                if( ( d[a[i][j]] + c[i][j] ) == d[i] ) 
                                {
                                    k=1;
                                    break;
                                }
                          }
                          
                          if(!k) ok = 0;
                    }
                }
            
            if(ok) printf("DA \n");
                   else printf("NU \n");
            T--;
    }
    
    return 0;
}