#include <fstream>
#include <vector>
#define inf 999999999
#define Nmax 50001
#define Mmax 100001
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int G,nh,n,m,sursa,poz[Nmax],h[Nmax],d[Nmax],sol[Nmax];
struct NOD{int nod,cost;};
vector<NOD> a[Mmax];
vector<NOD>::iterator it;
void citire(){
   NOD nd;int x,y,z;
   f>>n>>m>>sursa;
   for(int i=1 ; i<=n ; ++i)
   {
        f>>sol[i];
        a[i].clear();
   }
   for(int i=1 ; i<=m ; ++i)
   {
       f>>x>>y>>z;
       nd.nod=y;
       nd.cost=z;
       a[x].push_back(nd);
       nd.nod=x;
       a[y].push_back(nd);
   }
}
void schimba(int i,int j){
   int aux=h[i];
   h[i]=h[j];
   h[j]=aux;
   poz[ h[i] ]=i;
   poz[ h[j] ]=j;
}
void heap_up(int k){
   int t,fiu;
   fiu=k;
   t=k/2;
   while(t)
   {
       if(d[ h[t] ]>d[ h[fiu] ])
         schimba(t,fiu);
       else
        break;
       fiu=t;
       t/=2;
   }
}
void heap_down(int k){
   int t,fiu;
   t=1;
   fiu=2;
   while(fiu<=k)
   {
       if(fiu+1<=k&&d[ h[fiu] ]>d[ h[fiu+1] ])
         ++fiu;
       if(d[ h[t] ]>d[ h[fiu] ])
         schimba(t,fiu);
       else
         break;
       t=fiu;
       fiu*=2;
   }
}
int scot(){
   schimba(1,nh);
   --nh;
   heap_down(nh);
   return h[nh+1];
}
void dijkstra(int sursa){
   for(int i=1 ; i<=n ; ++i)
    d[i]=inf;
   d[sursa]=0;
   for(it=a[sursa].begin() ; it!=a[sursa].end() ; ++it)
    d[it->nod]=it->cost;

   for(int i=1 ; i<=n ; ++i)
      if(i!=sursa)
   {
       h[++nh]=i;
       poz[i]=nh;
       heap_up(nh);
   }

   while(nh)
   {
       int k=scot();
       for(it=a[k].begin() ; it!=a[k].end() ; ++it)
        if(d[it->nod]>d[k]+it->cost)
       {
           d[it->nod]=d[k]+it->cost;
           heap_up(poz[it->nod]);
       }
   }
}
int ok(){
   for(int i=1 ; i<=n ; ++i)
    if(d[i]!=sol[i])
     return 0;
   return 1;
}
int main()
{
    f>>G;
    for(int i=1 ; i<=G ; ++i)
    {
        citire();
        dijkstra(sursa);
        if(ok())
            g<<"DA"<<'\n';
        else
            g<<"NU"<<'\n';
    }
    return 0;
}