#include <cstdio>
#include <vector>
#define MAXN 50000
#define INF 2000000000
struct Edge{
   int nod;
   int val;
};
std::vector <Edge> G[MAXN+1];
inline void add_Edge(int a,int b,int c){
    G[a].push_back({b,c});
}
Edge H[5*MAXN+1];
inline int father(int nod){
   return nod/2;
}
inline int lson(int nod){
   return 2*nod;
}
inline int rson(int nod){
   return 2*nod+1;
}
inline void myswap(int x,int y){
    Edge aux=H[x];
    H[x]=H[y];
    H[y]=aux;
}
inline void urcare(int nod){
   while(father(nod)>0&&H[nod].val<H[father(nod)].val){
      myswap(nod,father(nod));
      nod=father(nod);
   }
}
inline void coborare(int nod,int n){
   int aux,flag=1;
   while(flag){
      aux=nod;
      if(lson(nod)<=n&&H[aux].val>H[lson(nod)].val)
        aux=lson(nod);
      if(rson(nod)<=n&&H[aux].val>H[rson(nod)].val)
        aux=rson(nod);
      if(aux==nod)
        flag=0;
      myswap(nod,aux);
      nod=aux;
   }
}
int d[MAXN+1];
int dist[MAXN+1];
inline char Dijkstra(int nod,int n){
   int i,nh,val,flag;
   for(i=1;i<=n;i++)
     dist[i]=INF;
   dist[nod]=0;
   flag=1;
   nh=1;
   H[nh].nod=nod;
   H[nh].val=0;
   while(nh>0&&flag==1){
      val=H[1].val;
      nod=H[1].nod;
      if(dist[nod]>val){
         dist[nod]=val;
         if(val!=d[nod])
           flag=0;
      }
      myswap(1,nh);
      nh--;
      coborare(1,nh);
      if(flag==1)
        for(i=0;i<G[nod].size();i++)
          if(dist[G[nod][i].nod]>val+G[nod][i].val){
             nh++;
             H[nh].nod=G[nod][i].nod;
             H[nh].val=G[nod][i].val+val;
             urcare(nh);
          }
   }
   return flag;
}
int main(){
   FILE*fi,*fout;
   int n,m,nod,t,i,a,b,c;
   fi=fopen("distante.in" ,"r");
   fout=fopen("distante.out" ,"w");
   fscanf(fi,"%d " ,&t);
   while(t>0){
      t--;
      fscanf(fi,"%d %d %d " ,&n,&m,&nod);
      for(i=1;i<=n;i++)
        fscanf(fi,"%d " ,&d[i]);
      for(i=1;i<=m;i++){
         fscanf(fi,"%d %d %d " ,&a,&b,&c);
         add_Edge(a,b,c);
         add_Edge(b,a,c);
      }
      if(Dijkstra(nod,n)==1)
        fprintf(fout,"DA\n");
      else
        fprintf(fout,"NU\n");
      for(i=1;i<=n;i++)
        G[i].clear();
   }
   fclose(fi);
   fclose(fout);
   return 0;
}