#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define NMax 50005

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

vector<int> v[NMax],w[NMax];

int T;
int n,m,s,i,ok;
int D[NMax],viz[NMax];
int nrn[NMax],nrt[NMax];
int a,b,c;

int solve()
{
    ok=1;

    queue<int> cd;

    f>>n>>m>>s;
    for(i=1;i<=n;++i)
    {
        f>>D[i];
        viz[i]=0;
        nrn[i]=0;
    }
    for(i=1;i<=m;++i)
    {
        f>>a>>b>>c;

        if(nrn[a]==nrt[a])
        {
            ++nrt[a];
            v[a].push_back(b);
            w[a].push_back(c);
        }
        else
        {
            v[a][nrn[a]]=b;
            w[a][nrn[a]]=c;
        }

        if(nrn[b]==nrt[b])
        {
            ++nrt[b];
            v[b].push_back(a);
            w[b].push_back(c);
        }
        else
        {
            v[b][nrn[b]]=a;
            w[b][nrn[b]]=c;
        }

        ++nrn[a];
        ++nrn[b];
    }

    if(D[s]!=0) ok=0;
    viz[s]=1;
    cd.push(s);

    while(!cd.empty())
    {
        s=cd.front();
        cd.pop();

        for(i=0;i<v[s].size();++i) if(viz[v[s][i]]==0)
        {
            if(D[s]+w[s][i]<D[v[s][i]]) ok=0;
            if(D[s]+w[s][i]==D[v[s][i]])
            {
                viz[v[s][i]]=1;
                cd.push(v[s][i]);
            }
        }
    }

    for(i=1;i<=n && ok;++i) if(viz[i]==0) ok=0;

    return ok;
}

int main()
{
    f>>T;
    while(T--) if ( solve() == 1) g<<"DA\n"; else g<<"NU\n";

    f.close();
    g.close();
    return 0;
}