#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]);

        if (dmin[sursa] != 0) printf("NU\n");
        else
        {
            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;

            }

            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;
}