#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(start!=i)
		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");
  
}
  
 

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);
 scanf("%d",&s);
 int dist[DIM];
 for (int i=1;i<=m;++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);
}

 
    
}