#include <fstream.h>
#define Nmax 50001
#define Mmax 100001
#define INF 10000000

typedef struct Nod { 
                   int inf,cost;
                   Nod * adr;
                   };
                   
typedef struct Nod * Lista;
typedef unsigned long vect[Nmax];

vect d,s,dr;
Lista G[Nmax];
int n,m,ns,t;

void inserare(Lista &p,int x,int c)
  {
  Lista nou;
  nou = new Nod;
  nou->inf=x;
  nou->cost=c;
  nou->adr=p;
  p=nou;
  }
ofstream fout("distante.out");
void dijkstra();
void afisare();

int det_cost(int x,int y)
  {
  Lista t;
  t=G[x];
  while(t)
    {
    if(t->inf==y) return t->cost;
    t=t->adr;
    }
  return INF;
}

void citire()
  {
  ifstream fin("distante.in");
  int i,x,y,c,k,j;
  fin>>t;
  for(k=1;k<=t;k++)
  {
  fin>>n>>m>>ns;
  for(i=1;i<=n;i++) {G[i]=NULL;fin>>dr[i];}
  for(i=1;i<=m;i++)
    {
    fin>>x>>y>>c;
    inserare(G[x],y,c);
    }
  if(dr[ns]) fout<<"NU"<<'\n';
  else
  {int ok=1;
  for(i=1;i<=n && ok;i++)
    {
    Lista t;
    t=G[i];
    while(t)
      {
      if(dr[i]+t->cost<dr[t->inf]) {ok=0;break;}
      t=t->adr;
      }
    }
  int ok2=0;
  for(i=1;i<=n;i++)
   if(i!=ns)
         for(j=1;j<=n;j++) if(i!=j && dr[j]==dr[i]+det_cost(i,j)) ok2=1;
  if(ok && ok2) fout<<"DA"<<'\n';
  else fout<<"NU"<<'\n';
   }
  //dijkstra();
  //afisare();
  }
  fin.close();
  
}

int min()
  {
  long min=INF,i,mini;
  for(i=1;i<=n;i++)
    if(!s[i] && min>d[i]) 
       {
       min=d[i];
       mini=i;
       }
  return mini;
}

int init()
  {
  int i;
  for(i=1;i<=n;i++) s[i]=0,d[i]=INF;
  Lista t;
  t=G[ns];
  while(t)
    {
    d[t->inf]=t->cost;
    t=t->adr;
    }
  s[ns]=1;
  d[ns]=0;
  }



void dijkstra()
  {
  int ok=0,nrp=0,poz,j,cost;
  init();
  do{
  poz=min();
  nrp++;
  if(nrp==n || d[poz]==INF) ok=1;
  else
     {
     s[poz]=1;
     for(j=1;j<=n;j++)
       {
       cost=det_cost(poz,j);
       if(!s[j] && d[j]>d[poz]+cost) d[j]=d[poz]+cost;
       }
     }
  }while(!ok); 
}


void afisare()
  {
  int i,ok=1;
  for(i=1;i<=n;i++) if(dr[i]!=d[i]) ok=0;
  if(ok) fout<<"DA"<<'\n';
  else fout<<"NU"<<'\n';
}

int main()
 {
 citire();
 fout.close();
 return 0;
}