#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 55000
#define INF 5000000
using namespace std;

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

int n, m, px;
int distInit[NMAX], dist[NMAX];

struct Element {
    int val, pos;
};

typedef struct {
    inline bool operator()(Element &el1, Element &el2) {
        return (el1.val > el2.val);
    }
} cmp;

priority_queue<Element, vector<Element>, cmp> pq;
vector <int> a[NMAX], cost[NMAX];

void read() {
    f >> n >> m >> px;
    px --;
    for (int i = 0; i < n; ++i) {
        f >> distInit[i];
    }
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        f >> x >> y >> c;
        x --;
        y --;
        a[x].push_back(y);
        a[y].push_back(x);
        cost[x].push_back(c);
        cost[y].push_back(c);
    }

}

void solve() {
    int *vis = new int[n + 1];
    for (int i = 0; i < n; ++i) {
        vis[i] = 0;
        dist[i] = INF;
    }
    Element el1;
    el1.pos = px;
    el1.val = 0;
    pq.push(el1);
    dist[px] = 0;

    for (int i = 0; i < n; ++i) {
        Element elCurent = pq.top();
        pq.pop();
        int valCurent = elCurent.val;
        int posCurent = elCurent.pos;
        if (vis[posCurent]) continue;

        vis[posCurent] = 1;
        for (int i = 0; i < a[posCurent].size(); ++i) {
            int vecin = a[posCurent][i];
            int costCrt = cost[posCurent][i];
            if (dist[vecin] > costCrt + valCurent) {
                dist[vecin] = costCrt + valCurent;
                Element el2;
                el2.pos = vecin;
                el2.val = dist[vecin];
                pq.push(el2);
            }
        }

    }

    while (!pq.empty()) {
        pq.pop();
    }

    delete[] vis;
}

void print() {
    bool corect = true;
    for (int i = 0; i < n; ++i) {
        if (dist[i] != distInit[i]) {
            corect = false;
        }
    }
    if (corect) g << "DA\n";
    else g << "NU\n";
}

int main() {
    int queryNumber;
    f >> queryNumber;
    while (queryNumber --) {
        read();
        solve();
        print();
        for (int i = 0; i < n; ++i) {
            a[i].clear();
            cost[i].clear();
        }
    }

    return 0;
}