#include <cstdio> 

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;
    
         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;
         }   
    }   
  
    void lift(int c)   
    {   
        int d;   
        while (c > 1)   
        {   
              d = c >> 1;   
              if (D[H[d]] > D[H[c]])   
              {   
                  P[H[c]] = d, P[H[d]] = c;   
                  int ax = H[d]; H[d] = H[c], H[c] = ax;
                  c = d;   
              }   
              else c = 1;   
        }   
    }   
  
    void sink(int c)   
    {   
        int d;   
        while (c <= k)   
        {   
            d = c;   
            if (c << 1 <= k)   
            {   
                d = c << 1;   
                if (d < k) if (D[H[d + 1]] < D[H[d]]) ++d;   
            } else return;   
  
            if (D[H[c]] > D[H[d]])   
            {   
                P[H[c]] = d, P[H[d]] = c;   
                int ax = H[d]; H[d] = H[c], H[c] = ax;   
                c = d;   
            } else return;   
        }   
     }   
  
     void solve()   
     {   
         int i;
         k = 0;
         for (i = 1; i <= N; ++i)   
             D[i] = INF, P[i] = -1;   
         D[S] = 0;
         P[S] = 1, H[++k] = S;   
  
         while (k)   
         {   
             int min = H[1];   
             int ax = H[1]; H[1] = H[k]; H[k] = ax;   
             P[H[1]] = 1;   
             --k, sink(1);   
             NOD *q = A[min];   
  
             while (q)   
             {   
                 if (D[q->nod] > D[min] + q->cost)   
                 {   
                     D[q->nod] = D[min] + q->cost;   
  
                     if (P[q->nod] != -1)   
                        lift(P[q->nod]);   
                     else   
                         H[++k] = q->nod, P[H[k]] = k, lift(k);      
                 }   
                 q = q->next;   
             }   
         }   
    }   
  
    int main()   
    {   
         freopen (FIN, "r", stdin);
         freopen (FOUT, "w", stdout);
    
         scanf ("%d", &T);
         while (T--)
         {
               readdata();   
               solve();   
  
               int ok = 1;
               for (i = 1; i <= N; ++i)   
                   if (D[i] == INF || D[i] != Dist[i]) ok = 0;
               if (ok) printf ("DA\n"); else printf ("NU\n"); 
         }
  
               return 0;   
    }