#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;

const int Nmax = 50000;
const int Mmax = 100000;
const int NIL = -1;
const int INF = 2e9;
const int Bsize = 65536;

int D[Nmax];
int d[Nmax];

char buffer[Bsize];
int ptr = Bsize;

inline char GetChar() {
    if (ptr == Bsize) {
        fread(buffer, 1, Bsize, stdin);
        ptr = 0;
    }
    return buffer[ptr++];
}

inline int ReadInt() {
    int q = 0;
    char c;

    do {
        c = GetChar();
    } while (!isdigit(c));
    do {
        q = (10 * q) + (c - '0');
        c = GetChar();
    } while (isdigit(c));
    return q;
}

struct List {
    int v, cost;
    int next;
};

List l[2 * Mmax];
int adj[Nmax];

int h[Nmax], hpos[Nmax];
int hSize;

void shift(int k) {
    int best, changed;

    do {
        best = k;
        changed = 0;
        if ((2 * k + 1 < hSize) && (d[best] > d[2 * k + 1])) {
            best = 2 * k + 1;
        }
        if ((2 * k + 2 < hSize) && (d[best] > d[2 * k + 2])) {
            best = 2 * k + 2;
        }
        if (best != k) {
            changed = 1;
            hpos[best] = k;
            hpos[k] = best;
            swap(h[best], h[k]);
            k = best;
        }
    } while (changed);
}

void percolate(int k) {
    int p = hpos[k];
    int father = (p - 1) / 2;

    while (p > 0 && d[p] < d[father]) {
        hpos[father] = p;
        hpos[p] = father;
        swap(h[p], h[father]);
        p = father;
        father = (p - 1) / 2;
    }
}

void inline addEdge(int u, int v, int cost, int pos) {
    l[pos].v = v;
    l[pos].cost = cost;
    l[pos].next = adj[u];
    adj[u] = pos;
}

int main(void) {
    freopen("distante.in", "r", stdin);
    freopen("distante.out", "w", stdout);
    int T, n, m, source;
    int u, v, cost;

    T = ReadInt();
    while (T--) {
        n = ReadInt();
        m = ReadInt();
        source = ReadInt() - 1;

        for (int i = 0; i < n; i++) {
            D[i] = ReadInt();
            adj[i] = NIL;
            d[i] = INF;
        }
        for (int i = 0; i < m; i++) {
            u = ReadInt() - 1;
            v = ReadInt() - 1;
            cost = ReadInt();
            addEdge(u, v, cost, 2 * i);
            addEdge(v, u, cost, 2 * i + 1);
        }
        d[source] = 0;
        h[0] = source;
        hSize = 1;
        hpos[source] = 0;
        do {
            u = h[0];
            h[0] = h[hSize - 1];
            hpos[h[0]] = 0;
            hSize--;
            shift(0);
            for (int i = adj[u]; i != NIL; i = l[i].next) {
                v = l[i].v;
                cost = d[u] + l[i].cost;
                if (d[v] > cost) {
                    d[v] = cost;
                    h[hSize] = v;
                    hpos[v] = hSize;
                    hSize++;
                    percolate(v);
                }
            }
        } while (hSize);
        u = 0;
        while (u < n && d[u] == D[u]) {
            u++;
        }
        puts((u == n) ? "DA" : "NU");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}