#include <stdio.h>
#include <algorithm>
#define inf 2000000000
#define nMax 50005
#define mMax 100005

using namespace std;

long d[nMax];
long q[nMax];
long poz[nMax];
long n,m,k,i,j,r;
long nod_min,C;
long x[mMax],y[mMax],z[mMax],G[nMax];
long *v[nMax],*c[nMax];

void scufunda(long i){
     long fiu;
     while ((long)(i<<1)<=k){
           fiu=i<<1;
           if ((long)(fiu|1)<=n)
              if (d[q[fiu|1]]<d[q[fiu]])fiu|=1;
           if (d[q[fiu]]<d[q[i]]){
              swap(q[i],q[fiu]);
              poz[q[i]]=i;
              poz[q[fiu]]=fiu;
              i=fiu;
           }
           else break;
     }
}

void ridica(long i){
     long val=q[i];
     while (i>1 && d[val]<d[q[i>>1]]){
           q[i]=q[i>>1];
           poz[q[i]]=i;
           i>>=1;
     }      
     q[i]=val;
     poz[q[i]]=i;
}

long get_min(){
     swap(q[1],q[k]);
     poz[q[1]]=1;
     poz[q[k]]=k;
     k--;
     scufunda(1);
     return q[k+1];
}

void dijkstra(){
     //initializare
     for (i=1;i<=n;i++){
         poz[i]=q[i]=i;
         d[i]=inf;
     }
     d[r]=0;
     k=n;
     while (k){
           nod_min=get_min();
           for (i=1;i<=G[nod_min];i++)
               if (d[j=v[nod_min][i]]>d[nod_min]+c[nod_min][i]){
                  d[j]=d[nod_min]+c[nod_min][i];
                  ridica(poz[j]);
               }
     }
}

int main(){
    freopen("distante.in","r",stdin);
    freopen("distante.out","w",stdout);
    
    long T,d_ver[nMax],ok;
    scanf("%ld",&T);
    while (T--){
          scanf("%ld %ld %ld",&n,&m,&r);
          for (i=1;i<=n;i++)scanf("%ld",&d_ver[i]);
          // r - nod sursa
          i=m;
          while (m){
                scanf("%ld %ld %ld",&x[m],&y[m],&z[m]);
                G[x[m]]++;
                m--;
          }
          m=i;
          for (i=1;i<=n;i++){
              v[i]=new long [G[i]+1];
              c[i]=new long [G[i]+1];
              G[i]=0;
          }
          for (i=1;i<=m;i++){
              v[x[i]][++G[x[i]]]=y[i];
              c[x[i]][G[x[i]]]=z[i];
          }
          dijkstra();
          ok=1;
          for (i=1;i<=n;i++)
              if (d[i]!=d_ver[i]){ok=0;break;}
          if (ok)printf("DA\n");
          else printf("NU\n");
    }

return 0;
}