#include <stdio.h>
#include <stdlib.h>
#define nmax 50001
#define infinit 2000000000
 
int T, N, M, i, sursa, x, y, c, j, min;
 
int dmin[nmax], *L[nmax], *C[nmax];
 
int main(void)
{
    freopen("distante.in", "r", stdin);
    freopen("distante.out", "w", stdout);
 
    scanf("%d", &T);
 
    while (T--)
    {
        scanf("%d%d%d", &N, &M, &sursa);
 
        for (i = 1; i <= N; ++i)
            scanf("%d", &dmin[i]);
 
        for (i = 1; i <= N; ++i)
            {
                L[i] = (int *)realloc(L[i], sizeof(int));
                C[i] = (int *)realloc(C[i], sizeof(int));
                C[i][0] = L[i][0] = 0;
            }
 
        for (i = 1; i <= M; ++i)
            {
                scanf("%d%d%d", &x, &y, &c);
 
                L[x][0]++;
                L[x] = (int *)realloc(L[x], (1 + L[x][0]) * sizeof(int));
                L[x][L[x][0]] = y;
 
                C[x][0]++;
                C[x] = (int *)realloc(C[x], (1 + C[x][0]) * sizeof(int));
                C[x][C[x][0]] = c;
 
                L[y][0]++;
                L[y] = (int *)realloc(L[y], (1 + L[y][0]) * sizeof(int));
                L[y][L[y][0]] = x;
 
                C[y][0]++;
                C[y] = (int *)realloc(C[y], (1 + C[y][0]) * sizeof(int));
                C[y][C[y][0]] = c;
            }
 
        if (dmin[sursa] != 0) printf("NU\n");
        else
        {
 
            for (i = 1; i <= N; ++i) if (i != sursa)
            {
                for (j = 1, min = infinit; j <= L[i][0]; ++j)
                    if (dmin[L[i][j]] + C[i][j] < min)
                       min = dmin[L[i][j]] + C[i][j];
 
                if (min != dmin[i])
                {
                   printf("NU\n");
                   i = N + 1;
                }
            }
 
            if (i != N + 2)
               printf("DA\n");
        }
    }
 
    return 0;
}