#include<cstdio>
#include<fstream>
#include<vector>
#include<queue>
    
#define INFINIT 1<<30
#define DIM 50001
 int dist[DIM]; int s;
    
using namespace std;
    
    int drum[DIM];
       
    
vector< pair<int,int> >graf[DIM];
    
void set_inf(int n)
{
      for(int i=1;i<=n;++i)
      {
        drum[i]=INFINIT;
    }
}
   
int ciclu[DIM];
int ok;
   
int print (int start,int n)
{
    if (ok)
      {
          for(int i=1;i<=n;++i){
        if(drum[i]==INFINIT)
            drum[i]=0;
    
     
        if(dist[i]!=drum[i])
            return 0;}
             
  return 1;
      }
}
   
   
   
void bellford(int start,int n){
    
   
    int nod;
    queue <int> queue_graf;
    
    set_inf(n);
     
    
    drum[start]=0;
    queue_graf.push(start);
    ok=1;
    
    while(queue_graf.empty()==0){
    
        nod=queue_graf.front();
        queue_graf.pop();
    
        for( int i=0; i<graf[nod].size();++i ){
    
            if(drum[nod]+graf[nod][i].second<drum[graf[nod][i].first])
                if (ciclu[graf[nod][i].first]<n)
            {
    
                drum[graf[nod][i].first]=drum[nod]+graf[nod][i].second;
                queue_graf.push(graf[nod][i].first);
                ciclu[graf[nod][i].first]++;
            }
                else
                    ok=0;
    
        }
    
    }
  if(print(start,n)) printf("DA\n");
else
 printf("NU\n");
    
}
    
void setdrum(int n)
{
	for(int i=1;i<=n;++i)
		drum[i]=0;
}
  
int main(){
    freopen("distante.in","r",stdin);
freopen("distante.out","w",stdout);
    int A,B,C,n,m;
    int t;
  
  scanf("%d",&t);
 for (int i=1;i<=t;++i)
{
	
  scanf("%d%d",&n,&m);
  setdrum(n);
 scanf("%d",&s);
 
 for (int i=1;i<=n;++i)
    scanf("%d",&dist[i]);
  
    for(int j=1;j<=m;j++){
                                                                                                         
            scanf("%d %d %d",&A,&B,&C);
            graf[A].push_back(make_pair(B, C));
    
        }
    
    bellford(s,n);
}
  
   
      
}