#include <bits/stdc++.h>
using namespace std;
   
ifstream in("distante.in");
ofstream out("distante.out");
 
const int NMax = 50005;
const int inf = 1e9;
 
vector< vector< pair< int, int > > > G(NMax);
vector< int > distante(NMax, inf);
 
void dijkstra(int nodSursa) {
    set< pair< int, int > > q;
    distante[nodSursa] = 0;
    q.insert(make_pair(0, nodSursa));
 
    while(!q.empty()) {
        int tempNode = q.begin()->second; q.erase(q.begin());
 
        for(auto vecin: G[tempNode]) {
            int len = vecin.second;
 
            if(distante[tempNode] + len < distante[vecin.first]) {
                q.erase(make_pair(distante[vecin.first], vecin.first));
                distante[vecin.first] = distante[tempNode] + len;
                q.insert(make_pair(distante[vecin.first], vecin.first));
            }
        }
    }
}
 
int main() {
  
    int T; in >> T;
 
    while(T--) {
        int n, m, nodSursa; in >> n >> m >> nodSursa;
 
        distante.resize(n + 1);
        for(int i = 1; i <= n; ++i) {
            distante[i] = inf;
        }
         
        vector< int > distanteBronzorel(n + 1);
        for(int i = 1; i <= n; ++i) {
            in >> distanteBronzorel[i];
        }
 
        for(int i = 1; i <= m; ++i) {
            int a, b, c; in >> a >> b >> c;
            G[a].push_back(make_pair(b, c));
            G[b].push_back(make_pair(a, c));
        }
 
        dijkstra(nodSursa);
 
        bool ok = true;
        for(int i = 1; i <= n && ok; ++i) {
            if(distante[i] != distanteBronzorel[i]) {
                out << "NU\n";
                ok = false;
            }
        }
 
        if(ok) {
            out << "DA\n";
        }
 
        for(int i =1; i <= n; ++i) {
            G[i].clear();
        }
    }
     
    in.close(); out.close();
   
    return 0;
}