/// Craciun Catalin
///  Distante
///   Dijkstra - heap-uri
#include <iostream>
#include <fstream>
#include <cstring>

#define log(___) cout<<"Console: "<<___<<'\n'
#define inf 1<<30
#define NMax 50005

using namespace std;

struct graf {

    int cost;
    int nod;
    graf *next;
    graf () {
        cost = nod = 0;
        next = NULL;
    }
};

ifstream f("distante.in");
ofstream g("distante.out");

int t;
int n, m;
graf *a[NMax];
int dist[NMax];
int poz[NMax];
int distEs[NMax];
int H[NMax]; /// Heap
int heapSize;

void swapH(int i, int j) {

    int aux = H[i];
    H[i] = H[j];
    H[j] = aux;

    poz[H[i]] = i;
    poz[H[j]] = j;
}

void compare() {

    bool ok = true;
    for (int i=1;i<=n;i++)
        if (distEs[i] != dist[i]) {
            ok = false;
            break;
        }

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

void downHeap(int x) {

    int pminim = -1;
    while (x != pminim) {
        pminim = x;
        int minim = dist[H[x]];

        if (2*x <= heapSize) {
            if (minim > dist[H[2*x]]) {
                minim = dist[H[2*x]];
                pminim = 2*x;
            }
        }
        if (2*x+1 <= heapSize) {
            if (minim > dist[H[2*x+1]]) {
                minim = dist[H[2*x+1]];
                pminim = 2*x+1;
            }
        }

        if (pminim != x) {
            swapH(x, pminim);
            x = pminim;
        }
    }
}

void upHeap(int x) {

    while (x > 1) {
        if (dist[H[x]] < dist[H[x/2]]) {
            swapH(x, x/2);
            x = x/2;
        } else {
            x = 1;
            break;
        }
    }
}

void dijkstra_heap(int source) {

    for (int i=1;i<=n;i++) {
        dist[i] = inf;
        poz[i] = -1;
    }

    dist[source] = 0;
    poz[source] = 1;
    H[++heapSize] = source;

    while (heapSize > 0) {
        int nodEx = H[1];
        swapH(1, heapSize);

        heapSize--;

        downHeap(1);

        graf *q = a[nodEx];
        while ( q ) {

            if (dist[q->nod] > dist[nodEx] + q->cost) {
                dist[q->nod] = dist[nodEx] + q->cost;

                if (poz[q->nod] != -1) {
                    upHeap(poz[q->nod]);
                } else {
                    heapSize++;
                    H[heapSize] = q->nod;
                    poz[q->nod] = heapSize;
                    upHeap(poz[q->nod]);
                }
            }

            q = q->next;
        }
    }
}

void add(int where, int what, int c) {

    graf *q = new graf;
    q->nod = what;
    q->cost = c;
    q->next = a[where];
    a[where] = q;
}

void read() {

    f>>t;
    for (int q=1;q<=t;q++) {
        int s;
        f>>n>>m>>s;

        for (int i=1;i<=n;i++)
            a[i] = NULL;
        heapSize = 0;

        for (int i=1;i<=n;i++)
            f>>distEs[i];
        for (int i=1;i<=m;i++) {
            int x,y,c;
            f>>x>>y>>c;
            add(x,y,c);
            add(y,x,c);
        }

        dijkstra_heap(s);
        compare();
    }
}

int main() {

    read();
    f.close(); g.close();

    return 0;
}