#include <bits/stdc++.h>
#define in "distante.in"
#define out "distante.out"
#define INF 0x3f3f3f3f
#define MN 50005
using namespace std;
struct nod
{
    int vrf, cst;
    nod* next;
};
typedef nod* graf;
graf A[MN];
int D[MN], H[MN], Poz[MN], InputSol[MN], T, N, M, S, k;

void add(int srs, int vrf, int cst)
{
    graf p = new nod;
    p->vrf = vrf;
    p->cst = cst;
    p->next = A[srs];
    A[srs] = p;
}

void heap_sift(int poi)
{
    int cpl;
    while(poi <= k)
    {
        cpl = poi<<1;
        if(cpl <= k)
        {
            if(cpl+1 <= k && D[H[cpl+1]] < D[H[cpl]])
                cpl++;
        }
        else return;

        if(D[H[cpl]] < D[H[poi]])
        {
            Poz[H[poi]] = cpl;
            Poz[H[cpl]] = poi;
            swap(H[cpl], H[poi]);
            poi = cpl;
        }
        else return;
    }
}

void heap_percolate(int poi)
{
    int tte;
    while(poi > 1)
    {
        tte = poi>>1;
        if(D[H[poi]] < D[H[tte]])
        {
            Poz[H[poi]] = tte;
            Poz[H[tte]] = poi;
            swap(H[poi], H[tte]);
            poi >>= 1;
        }
        else return;
    }
}

void dijkstra()
{
    for(int i = 1; i <= N; ++i)
        D[i] = INF, Poz[i] = -1, H[i] = 0;
    D[S] = 0;
    Poz[S] = H[k=1] = S;
    while(k)
    {
        int pmc = H[1];
        swap(H[1], H[k]);
        Poz[H[1]] = 1;
        --k;
        heap_sift(1);
        graf q = A[pmc];
        while(q)
        {
            if(D[q->vrf] > D[pmc] + q->cst)
            {
                D[q->vrf] = D[pmc] + q->cst;
                if(Poz[q->vrf] == -1)
                {
                    H[++k] = q->vrf;
                    Poz[H[k]] = k;
                    heap_percolate(k);
                }
                else heap_percolate(Poz[q->vrf]);
            }
            q = q->next;
        }
    }
}

bool matching()
{
    for(int i = 1; i <= N; ++i)
        if(D[i] != InputSol[i])
            return 0;
    return 1;
}

void afis_muchii()
{
    for(int i = 1; i <= N; ++i)
    {
        assert(printf("%d: ", i));
        graf q = A[i];
        if(q == 0) assert(printf("%d", 0));
        while(q)
        {
            assert(printf("(%d, %d) ", q->vrf, q->cst));
            q = q->next;
        }
        assert(printf("\n"));
    }
}

int main()
{
    assert(freopen(in, "r", stdin));
    assert(freopen(out,"w", stdout));
    assert(scanf("%d", &T));
    while(T--)
    {
        assert(scanf("%d%d%d", &N, &M, &S));
        for(int i = 1; i <= N; ++i)
            assert(scanf("%d", InputSol+i));
        memset(A, 0, sizeof(A));
        for(int a, b, c; M; --M)
        {
            assert(scanf("%d%d%d", &a, &b, &c));
            add(a, b, c), add(b, a, c);
        }
        dijkstra();
        afis_muchii();
        assert(printf("%s\n", (matching()?"DA":"NU")));
    }
    fclose(stdin), fclose(stdout);
    return 0;
}