#include<fstream>
#include<iostream>
#include<set>
#include<vector>
using namespace std;
int estimare[50005],src,t,n,m,i,j,viz[50005],r[50005],q,a,b,minim,contor,x,y,z,w;
set< pair<int,int> > s;
vector <int> v[50005],d[50005];
int main()
{
    ifstream in("distante.in");
    ofstream out("distante.out");
    in>>t;
    for(int idx = 0; idx < t; idx++)
    {
        in>>n>>m>>src;
        s.clear();
        contor = 0;
        for(i=1;i<=n;i++)
        {
            in>>estimare[i];
            r[i]=1<<30;
            viz[i]=0;
            v[i].clear();
            d[i].clear();

        }
        r[src]=0;
        for(i=1;i<=m;i++)
        {
            in>>x>>y>>z;
            v[x].push_back(y);
            d[x].push_back(z);
        }
        s.insert(make_pair(0,src));
        contor++;
        while(contor>0)
        {
            w=s.begin()->first;
            q=s.begin()->second;
            if(viz[q]==1)
            {
                s.erase(s.begin());
                contor--;
            }
            else
            {
                viz[q]=1;
                minim=1<<30;
                for(i=0;i<v[q].size();i++)
                {
                    if(r[v[q][i]]>r[q]+d[q][i])
                    {

                        r[v[q][i]]=r[q]+d[q][i];
                        s.insert(make_pair(r[v[q][i]],v[q][i]));
                        contor++;

                    }

                }
            }

        }
        bool ok = 1;
        for(i=1;i<=n;i++)
        {
            if(r[i] != estimare[i])
                ok=0;
           /* if(r[i]==1<<30)
                out<<"0 ";
            else
                out<<r[i]<<' ';*/
        }
        if(ok==0)
            out<<"NU";
        else
            out<<"DA";
        out<<'\n';
    }


}