#include <fstream>
#include <vector>
#include <set>
#define nmax 50001

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m;
vector <pair<int,int> > v[nmax];
set<pair<int,int>>s;

int viz[nmax];
int d[nmax],dist[nmax];

void dijkstra(int x)
{
    int i;
    for(i=1; i<=n; i++) d[i]=1e9;
    d[x]=0;
    for(i=1; i<=n; i++) viz[i]=0;
    while(s.size()) s.erase(s.begin());
    s.insert({0,x});
    while(!s.empty())
        {
            int dist=s.begin()->first;
            int nod=s.begin()->second;
            int ct=v[nod].size();
            s.erase(s.begin());
            for(int i=0; i<ct; i++)
               {
                   int dist2=v[nod][i].second;
                   int nod_vec=v[nod][i].first;
                   if(!viz[nod_vec])
                      {
                          if(d[nod_vec]>dist+dist2)
                             {
                                 s.erase(make_pair(d[nod_vec],nod_vec));
                                 d[nod_vec]=dist+dist2;
                                 s.insert(make_pair(d[nod_vec],nod_vec));

                             }
                      }
               }
            viz[nod]=1;
        }

}

void read()
{
    int T;
    fin>>T;
    int i,j;
    for(j=1; j<=T; j++)
        {
            int node;
            fin>>n>>m>>node;
            for(i=1; i<=n; i++)
                 fin>>dist[i];
            for(int i=1;i<=n;i++)
                v[i].clear();
            int i,x,y,z;
            for(i=1; i<=m; i++)
                {
                    fin>>x>>y>>z;
                    v[x].push_back(make_pair(y,z));
                }
            dijkstra(node);
            int pp=0;
            for(i=1; i<=n; i++)
                 if(dist[i]!=d[i]) {fout<<"NU\n"; pp=1;break;}
            if(pp==0) fout<<"DA\n";

        }

}

int main()
{
    read();

    return 0;
}