#include <stdio.h>
#include <vector>

using namespace std;

int n, m, d[50001], dist[50001], start, heap[50001], posinheap[50001];
vector<int> v[50001], cost[50001];

void make_minheap();
void riseup(int nod);
void godown(int nod);
void dijkstra(int nod);

int main()
{
    freopen("distante.in", "r", stdin);
    freopen("distante.out", "w", stdout);

    int t, test, i, a, b, c, ok;

    scanf("%d", &t);

    for(test = 0; test < t; ++test)
    {
        scanf("%d %d %d", &n, &m, &start);
        for(i = 1; i <= n; ++i)
        {
            scanf("%d", &d[i]);
        }
        for(i = 0; i < n; ++i)
        {
            scanf("%d %d %d", &a, &b, &c);
            v[a].push_back(b);
            cost[a].push_back(c);
        }
        for(i = 1; i <= n; ++i)
        {
            dist[i] = 10000000;
            heap[i] = i;
            posinheap[i] = i;
        }
        dist[start] = 0;
        heap[0] = n;
        make_minheap();
        dijkstra(start);
        ok = 1;
        /*
        for(i = 1; i <= n; ++i)
        {
            printf("%d ", dist[i]);
        }
        */
        for(i = 1; i <= n && ok; ++i)
        {
            if(dist[i] != d[i])
            {
                printf("NU\n");
                ok = 0;
            }
        }
        if(ok)
        {
            printf("DA\n");
        }
        memset(heap, 0, sizeof(heap));
        memset(posinheap, 0, sizeof(posinheap));
        for(i = 1; i <= n; ++i)
        {
            vector<int> ().swap(v[i]);
            vector<int> ().swap(cost[i]);
        }
    }


    return 0;
}

void make_minheap()
{
    int i;
    for(i = n / 2; i > 0; --i)
    {
        godown(i);
    }
}

void godown(int nod)
{
    int fs = 2 * nod, fd = 2 * nod + 1, min = nod, temp;

    if(fs <= heap[0] && dist[heap[min]] > dist[heap[fs]])
    {
        min = fs;
    }
    if(fd <= heap[0] && dist[heap[min]] > dist[heap[fs]])
    {
        min = fd;
    }

    if(min != nod)
    {
        temp = heap[nod];
        heap[nod] = heap[min];
        heap[min] = temp;
        posinheap[heap[nod]] = nod;
        posinheap[heap[min]] = min;
        godown(min);
    }
}

void riseup(int nod)
{
    int temp;
    if(nod != 1)
    {
        if(dist[heap[nod]] < dist[heap[nod / 2]])
        {
            temp = heap[nod];
            heap[nod] = heap[nod / 2];
            heap[nod / 2] = temp;
            posinheap[heap[nod]] = nod;
            posinheap[heap[nod / 2]] = nod / 2;
            riseup(nod / 2);
        }
    }
}

void dijkstra(int nod)
{
    int i, sz;

    while(heap[0])
    {
        sz = v[heap[1]].size();
        for(i = 0; i < sz; ++i)
        {
            if(dist[heap[1]] + cost[heap[1]][i] < dist[v[heap[1]][i]])
            {
                dist[v[heap[1]][i]] = dist[heap[1]] + cost[heap[1]][i];
                riseup(posinheap[v[heap[1]][i]]);
            }
        }
        heap[1] = heap[heap[0]];
        posinheap[heap[1]] = 1;
        --heap[0];
    }
}