#include <vector>
#include <fstream>
#include <queue>
#include <string.h>
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
const int oo=2000000000;
const int NMAX=50000;
vector < pair <int,int> >G[NMAX+5];
int n,m,p,k,D[NMAX+5],D2[NMAX+5];
struct cmpD{

 bool operator()(int x,int y)
 {
     return D[x] > D[y];
 }
};
priority_queue< int ,vector <int>, cmpD >Q;
void read()
{
   f>>n>>m>>p;
   for(int i=1;i<=n;i++)
   {
       f>>D2[i];
   }
   for(int j=1;j<=m;j++)
   {
       int x,y,z;
       f>>x>>y>>z;
       G[x].push_back(make_pair(y,z));
   }
}
bool InCoada[NMAX+5];
void Dijkstra(int nodSTART)
{
    for(int i=1;i<=n;i++)
    {
        if(i!=p) D[i]=oo;
    }
    Q.push(nodSTART);
    InCoada[nodSTART]=1;
    while(!Q.empty())
    {
        int nodCurent= Q.top();
        Q.pop();
        InCoada[nodCurent]=0;
        for(int j=0;j<(int)G[nodCurent].size();j++)
        {
            int vecin=G[nodCurent][j].first;
            int cost=G[nodCurent][j].second;
            if(D[nodCurent]+cost<D[vecin])
            {
            D[vecin]=D[nodCurent]+cost;
            if(!InCoada[vecin])
            {
                Q.push(vecin);
                InCoada[vecin]=1;
            }
            }
        }
    }
}
bool check()
{
    for(int i=1;i<=n;i++)
    {
        if(D[i]!=D2[i]) return 0;
    }
    return 1;
}
int main()
{
    f>>k;
    for(int i=1;i<=k;i++)
    {
    read();
    Dijkstra(p);
    if(check()) g<<"DA"<<'\n';
    else g<<"NU"<<'\n';
    memset(InCoada,0,sizeof InCoada);
    memset(D,0,sizeof D);
    memset(D2,0,sizeof D2);
    for(int j=1;j<=n;j++)
    {
        G[j].clear();
    }
    }
    return 0;
}