#include <fstream>
#define INF (1 << 30)
#define N 50001
#include <queue>
std::ifstream fin("distante.in");
std::ofstream fout("distante.out");
int T, dist[N];
std::vector<std::vector<std::pair<int, int>>> V;
std::vector<int> computeDist(const std::vector<std::vector<std::pair<int, int>>>& V, int n, int start){
    std::vector<int> dist(n + 1, INF);
    std::queue<std::pair<int, int>> Q;
    Q.push({0, start});
    dist[start] = 0;
    while(!Q.empty()){
        int node = Q.front().second;
        Q.pop();
        for(std::pair<int, int> it : V[node]){
            if(dist[node] + it.second < dist[it.first]){
                dist[it.first] = dist[node] + it.second;
                Q.push({dist[it.first], it.first});
            }
        }
    }

    return dist;
}
int main(){
    fin >> T;
    int n, m, start;
    std::vector<int> dist, cdist;
    for(int i = 1; i <= T; i++){
        fin >> n >> m >> start;
        cdist = std::vector<int> (n + 1);
        int d;
        for(int j = 1; j <= n; j++){
            fin >> d;
            cdist[j] = d;
        }
        V = std::vector<std::vector<std::pair<int, int>>> (n + 1);
        int x, y, c;
        for(int j = 1; j <= m; j++){
            fin >> x >> y >> c;
            V[x].push_back({y, c});
        }
        dist = computeDist(V, n, start);
        int ok = 0;
        for(int i = 1; i <= n; i++){
            if(cdist[i] != dist[i])
                ok = 1;
        }
        fout << ((ok == 1) ? "NU" : "DA") << "\n";
        V.clear(); dist.clear();
    }
}