#include <bits/stdc++.h>

using namespace std;

vector< pair<int, int> > L[50005];
bool viz[50005];
int d[50005];
int D[50005];

int h[1000005], H;

void jos(int poz) {
    int son;
    do {
        son = 0;
        if(poz * 2 <= H) {
            son = poz * 2;
            if(son <= H && d[h[son]] > d[h[son + 1]])
                son ++;
            if(d[h[poz]] <= d[h[son]])
                son = 0;
        }
        if(son) {
            int aux = h[poz];
            h[poz] = h[son];
            h[son] = aux;
            poz = son;
        }
    }
    while(son);
}

void urc(int poz) {
    int aux = h[poz];
    while(poz > 1 && d[h[poz >> 1]] > d[aux]) {
        h[poz] = h[poz >> 1];
        poz >>= 1;
    }
    h[poz] = aux;
}

void scot() {
    h[1] = h[H];
    H --;
    jos(1);
}

void bag(int nr) {
    H ++;
    h[H] = nr;
    urc(H);
}

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

    int t;
    f >> t;
    while(t) {
        int n, m, s, a, b, c;
        f >> n >> m >> s;
        int lim = m << 2;
        for(int i = 1; i <= lim; i ++)
            h[i] = 100000000;
        for(int i = 1; i <= n; i ++)
            f >> D[i];
        for(int i = 1; i <= m; i ++) {
            f >> a >> b >> c;
            L[a].push_back(make_pair(b, c));
            L[b].push_back(make_pair(a, c));
        }

        for(int i = 1; i <= n; i ++)
            viz[i] = false;
        d[s] = 0;
        h[1]= s;
        H = 1;
        while(H) {
            int poz = h[1];
            scot();
            while(viz[poz]) {
                poz = h[1];
                scot();
            }
            viz[poz] = true;
            for(int j = 0; j < L[poz].size(); j ++) {
                if(!viz[L[poz][j].first] && d[L[poz][j].first] > d[poz] + L[poz][j].second) {
                    d[L[poz][j].first] = d[poz] + L[poz][j].second;
                    bag(L[poz][j].first);
                }
            }
        }
        bool ok = true;
        for(int i = 1; i <= n; i ++) {
            if(d[i] != D[i])
                ok = false;
            L[i].clear();
        }
        if(!ok)
            g << "NU\n";
        else g << "DA\n";
        t --;
    }
    return 0;
}