#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);
}
 
  
     
}