#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

#define INPUT "distante.in"
#define OUTPUT "distante.out"
#define pb push_back
#define mp make_pair
#define SET(X) memset(X, 0, sizeof(X))

const long NMAX = 50001;
const long INFI = (1 << 31) - 1;

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

long N, M, S, Poz;
long CostPrec[ NMAX ], Cost[ NMAX ], Heap[ NMAX ], PHeap[ NMAX ];
bool viz[ NMAX ];
vector< pair< long, long > > List[ NMAX ];

void resetData()
{
  for(long i = 1; i <= N; ++i)
    List[ i ].clear();
}

void readData()
{
  long Node1, Node2, C;
  
  fscanf(fin, "%ld %ld %ld", &N, &M, &S);
  
  for(long i = 1; i <= N; ++i)
    fscanf(fin, "%ld", &CostPrec[ i ]);
  
  for(long i = 1; i <= M; ++i)
  {
    fscanf(fin, "%ld %ld %ld", &Node1, &Node2, &C);
    
    List[ Node1 ].pb(mp(Node2, C));
    List[ Node2 ].pb(mp(Node1, C));
  }
}

void UpHeap(long P)
{
  while(P >= 1)
  {
    if(Cost[ Heap[ P ] ] < Cost[ Heap[ P/2 ] ])
    {
      swap(Heap[ P ], Heap[ P/2 ]);
      
      PHeap[ Heap[ P ] ] = P;
      PHeap[ Heap[ P/2 ] ] = P/2;
      
      P/=2;
    }
    else return;
  }
}

void DownHeap(long P)
{
  long p = P;
  long pi;
  
  while(p <= Poz)
  {
    if(2 * p <= Poz)
    {
      pi = 2 * p;
      
      if(pi+1 <= Poz && Cost[ Heap[ pi ] ] > Cost[ Heap[ pi+1 ]]) ++pi;
      
      if(Cost[ Heap[ pi ] ] < Cost[ Heap[ p ] ])
      {
        swap(Heap[ P ], Heap[ p ]);
        
        PHeap[ Heap[ P ] ] = P;
        PHeap[ Heap[ p ] ] = p;
        
        P = p;
      }
      else return;
    }
    else return;
  }
}

void dijkstra()
{
  for(long i = 1; i <= N; ++i)
    Cost[ i ] = INFI, viz[ i ] = false;
  
  Poz = 0;
  vector< pair< long, long > >::iterator it;
  long Node;
  
  Cost[ S ] = 0;
  viz[ S ] = 1;
  Heap[ ++Poz ] = S;
  PHeap[ S ] = Poz;
  
  for(;Poz > 0;)
  {
    Node = Heap[ 1 ];
    Heap[ 1 ] = Heap[ Poz-- ];
    
    DownHeap(1);
    
    for(it = List[ Node ].begin(); it != List[ Node ].end(); ++it)
      if(!viz[ it -> first ])
      {
        viz[ it ->first ] = true;
        Heap[ ++Poz ] = it -> first;
        PHeap[ it -> first ] = Poz;
        Cost[ it -> first ] = Cost[ Node ] + it -> second;
        
        UpHeap(Poz);
      }
      else
      if(Cost[ it -> first ] > Cost[ Node ] + it -> second)
        Cost[ it -> first ] = Cost[ Node ] + it -> second;
  }
  
  for(long i = 1; i <= N; ++i)
  {
    if(Cost[ i ] == INFI) Cost[ i ] = 0;
    
    if(Cost[ i ] != CostPrec[ i ])
    {
      fprintf(fout, "NU\n");
      return;
    }
  }
  
  fprintf(fout, "DA\n");
}

int main()
{
  int T;
  
  fscanf(fin, "%d", &T);
  
  for(;T--;)
  {
    if(N) resetData();
    readData();
    
    SET(Heap);
    SET(PHeap);
    dijkstra();
  }
  
  fclose(fin);
  fclose(fout);
  
  return 0;
}