#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;

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

#define NMAX 50005
#define INF 50000005

int t, n, m, s, valori[NMAX];
vector<pair<int, int>> G[NMAX];
int d[NMAX];
bitset<NMAX> viz;
priority_queue<pair<int, int>> q;

void citire_graf() {
    for (int i = 1; i <= n; i++)
        f >> valori[i];
    int nod1, nod2, cost;
    for (int i = 0; i < m; i++) {
        f >> nod1 >> nod2 >> cost;
        G[nod1].push_back({cost, nod2});
    }
}

void initializare() {
    viz.reset();
    for (int i = 1; i <= n; i++) {
        d[i] = INF;
        G[i].clear();
    }
    d[s] = 0;
}

void parcurgere() {
    int vf = s;
    while (true) {
        viz[vf] = true;
        for (auto &nod:G[vf])
            if (!viz[nod.second] && d[vf] + nod.first < d[nod.second]) {
                d[nod.second] = d[vf] + nod.first;
                q.push({-d[nod.second], nod.second});
            }
        while (!q.empty() && viz[q.top().second])
            q.pop();
        if (q.empty())
            break;
        vf = q.top().second;
    }
}

void afisare() {
    for (int i = 1; i <= n; i++)
        if (d[i] != valori[i]) {
            g << "NU\n";
            return;
        }
    g << "DA\n";
}

int main() {
    f >> t;
    for (int i = 0; i < t; i++) {
        f >> n >> m >> s;
        initializare();
        citire_graf();
        parcurgere();
        afisare();
    }
    return 0;
}