#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
#define inf 999999999

using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int T,k;
int H[50005],lung[50005],lung_orig[50005],poz[50005];

struct elem
{
    int dest,val;
};
vector<elem> vect[50005];

inline int dad(int);
inline int firstson(int);
inline int secondson(int);
inline void sift(int);
inline void percolate(int);

int main()
{
    f>>T;
    while (T--)
    {
        int N,M,S;
        f>>N>>M>>S;
        FOR (i,1,N) {
            vect[i].clear();
        }
        FOR (i,1,N)
            f>>lung_orig[i];
        FOR (i,1,M) {
            int a,b,c;
            f>>a>>b>>c;
            elem A,B;
            A.dest=b;
            B.dest=a;
            A.val=B.val=c;
            vect[a].pb(A);
            vect[b].pb(B);
        }
        FOR (i,1,N) {
            poz[i]=-1;
            lung[i]=inf;
        }
        k=1;
        lung[S]=0;
        H[1]=S;
        poz[S]=1;
        while (k)
        {
            int x=H[1];
            swap(H[1],H[k]);
            poz[H[1]]=1;
            --k;
            sift(1);
            for (unsigned int j=0;j<vect[x].size();++j) {
                if (lung[vect[x][j].dest]>lung[x]+vect[x][j].val) {
                    lung[vect[x][j].dest]=lung[x]+vect[x][j].val;
                    if (poz[vect[x][j].dest]==-1) {
                        H[++k]=vect[x][j].dest;
                        poz[vect[x][j].dest]=k;
                        percolate(k);
                    }
                    else {
                        percolate(poz[vect[x][j].dest]);
                    }
                }
            }
        }
        bool ok=true;
        FOR (i,1,N)
            if (lung[i]!=lung_orig[i]) {
                ok=false;
                break;
            }
        if (ok) g<<"DA\n";
        else g<<"NU\n";
    }
    f.close();g.close();
    return 0;
}

inline int dad(int nod)
{
    return nod>>1;
}

inline int firstson(int nod)
{
    return nod<<1;
}

inline int secondson(int nod)
{
    return (nod<<1)+1;
}

inline void percolate(int nod)
{
    while (nod>1 && lung[H[nod]]<lung[H[dad(nod)]])
    {
        swap(poz[H[nod]],poz[H[dad(nod)]]);
        swap(H[nod],H[dad(nod)]);
        nod=dad(nod);
    }
}

inline void sift(int nod)
{
    int son;
    do {
        son=0;
        if (firstson(nod)<=k) {
            son=firstson(nod);
            if (secondson(nod)<=k && lung[H[secondson(nod)]]<lung[H[son]])
                son=secondson(nod);
            if (lung[H[son]]>=lung[H[nod]])
                son=0;
        }
        if (son) {
            swap(poz[H[son]],poz[H[nod]]);
            swap(H[son],H[nod]);
            nod=son;
        }
    }
    while(son);
}