#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

#define inf 1 << 30
using namespace std;
ifstream fin("distante.in");
ofstream fout("distante.out");
int n, m, node, D[50005], a, new_node, bestD[50005], T;
struct lista{
  int vecin, dist;
}x;
vector <lista> v[50005];
queue <int> C;
bitset <50005> is_in_tail;
void bfs(int x){
   C.push(x);
   bestD[x] = 0;
   is_in_tail[x] = 1;
  while(!C.empty()){
    node = C.front();
    is_in_tail[node] = 0;
    C.pop();
    for(int i = 0; i < v[node].size(); ++i){
        new_node = v[node][i].vecin;
        if(bestD[node] + v[node][i].dist < bestD[new_node]){
            bestD[new_node] = bestD[node] + v[node][i].dist;
            if(!is_in_tail[new_node]){
             C.push(new_node);
             is_in_tail[new_node] = 1;
            }
        }
    }
  }
}
int is_ok(){
  for(int i = 1; i <= n; ++i)
    if(D[i] != bestD[i]) return 0;
    return 1;
}
void read()
{
  fin >> T;
  for(int j = 1; j <= T; ++j){
    fin >> n >> m >> node;
    for(int i = 1; i <= n; ++i)
        fin >> D[i];
    for(int i = 1; i <= m; ++i){
        fin >> a >> x.vecin >> x.dist;
        v[a].push_back(x);
        swap(a, x.vecin);
        v[a].push_back(x);
    }
    for(int i = 1; i <= n; ++i)
        bestD[i] = inf;
    bfs(node);
    for(int i = 1; i <= n; ++i){
        if(bestD[i] == inf) bestD[i] = 0;
        v[i].clear();
    }
    if(is_ok()) fout << "DA\n";
      else fout << "NU\n";
  }
}
int main()
{
    read();
    return 0;
}