#include <stdio.h>
#define MAX 50001
#define _INFINITY 2000000001

const char Infile[] = "distante.in";
const char Outfile[] = "distante.out";

struct node {
       int v, cost;
       node *next;
} *graph[MAX];

int sel1[MAX], sel[MAX], d[MAX], h[MAX], pos[MAX], n, hsize, source, tnr, gd[MAX];

void ReadData();
void Add(int i, int j, int c);
void BuildHeap();
void InsertHeap(int vertex);
void MoveUp(int vertex);
void Dijkstra();
void Print();
inline int ExtractMin();
inline int LeftSon(int x);
inline int Parent(int x);

int main()
{
	freopen(Infile, "r", stdin);
    freopen(Outfile, "w", stdout);

    scanf("%d", &tnr);

    while ( tnr )
    {
		ReadData();
        Dijkstra();
        Print();
        tnr--;
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}

void ReadData()
{
    int i = 0, x = 0, y = 0, c = 0, m = 0;
    scanf("%d %d %d", &n, &m, &source);

    for ( i = 1; i <= n; i++ )
        scanf("%d", gd + i);

    for ( i = 1; i <= m; i++ )
    {
        scanf("%d %d %d", &x, &y, &c);
        Add(x, y, c);
        Add(y, x, c);
    }
}

void Add(int i, int j, int c)
{
    node *x = new node;
    x->v = j;
    x->cost = c;
    if ( sel1[i] != tnr )
    {
        sel1[i] = tnr;
        graph[i] = NULL;
    }
    x->next = graph[i];
    graph[i] = x;
}

void BuildHeap()
{
    node *x = NULL;

    for ( int i = 1; i <= n; i++ )
        d[i] = _INFINITY;

    d[source] = 0;    
    for ( x = graph[source]; x; x = x->next )
    {
        d[x->v] = x->cost;
        InsertHeap(x->v);   // insereaza un varf v
        sel[x->v] = 1;
    }
}

void InsertHeap(int vertex)  // minheap
{
    int son = 0, parent = 0;

    son = ++hsize; // n
    parent = Parent(son);  // parent = son / 2;

    while ( parent && d[h[parent]] > d[h[son]] )
    {
        h[son] = h[parent];
        pos[h[son]] = son;
        son = parent;
        parent = Parent(son);
    }

    h[son] = vertex;
    pos[vertex] = son;
}

void MoveUp(int vertex)
{
    int son = 0, parent = 0;

    son = pos[vertex];
    parent = Parent(son);  // son / 2

    while ( parent && d[h[parent]] > d[h[son]] )
    {
        h[son] = h[parent];
        pos[h[son]] = son;
        son = parent;
        parent = Parent(son);
    }

    h[son] = vertex;
    pos[vertex] = son;
}

void RebuildHeap(int i)
{
    int value = 0, son = 0, parent = 0;
    
    value = h[i];
    parent = i;
    son = LeftSon(parent);  // son = 2 * parent

    while ( son <= hsize )
    {
        if ( son < hsize )
           if ( d[h[son]] > d[h[son+1]] ) son++;
                if ( d[value] > d[h[son]] )
                {
                    h[parent] = h[son];
                    pos[h[parent]] = parent;
                    parent = son;
                    son = LeftSon(son);
                }
                else break;
    }

    h[parent] = value;
    pos[value] = parent;
}

void Dijkstra()
{
    int u = 0;
    node *x = NULL;
    BuildHeap();

    while ( hsize )
    {
        u = ExtractMin();
        sel[u] = 0;
        for ( x = graph[u]; x; x = x->next )
            if ( d[x->v] > d[u] + x->cost )
            {
                d[x->v] = d[u] + x->cost;
                if ( sel[x->v] ) 
                    MoveUp(x->v); // in Heap
                else
                {
                    InsertHeap(x->v);
                    sel[x->v] = 1;
                }
            }
    }
}

void Print()
{
    int i = 0, ok = 1;
    for ( i = 1; i <= n; i++ )
        if ( gd[i] != d[i] )
        {
           ok = 0;
           break;
        }

    if ( ok ) 
        printf("DA\n");
   else 
        printf("NU\n");
}

int ExtractMin()
{
    int min = h[1];
    h[1] = h[hsize--];
    RebuildHeap(1);

    return min;
}

inline int LeftSon(int x)
{
    return 2 * x;
}

inline int Parent(int x)
{
    return x / 2;
}