#include <bits/stdc++.h>
#define newline '\n'
#define STOP fin.close(); fout.close(); return 0;
using namespace std;
ifstream fin("distante.in");
ofstream fout("distante.out");
///***********************
const int NMAX = 5e4 + 3;
struct Edge {
    int to, cost;
    bool operator < (const Edge &other) const {
        return cost > other.cost;
    }
};
int n, m, s;
vector<Edge> graph[NMAX];
vector<int> dis, trueDis;

void read() {
    fin >> n >> m >> s;
    trueDis = dis = vector<int>(n, 1e9);
    for (int &it : dis)
        fin >> it;
    for (int a, b, c, i = 0; i < m; i++) {
        fin >> a >> b >> c;
        a--, b--;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
}

void dijkstra(int start) {
    priority_queue<Edge> q;
    q.push({start, 0});
    trueDis[start] = 0;
    while (!q.empty()) {
        int node = q.top().to;
        q.pop();
        for (auto it : graph[node]) {
            if (trueDis[it.to] > trueDis[node] + it.cost) {
                trueDis[it.to] = trueDis[node] + it.cost;
                it.cost = trueDis[it.to];
                q.push(it);
            }
        }
    }
}

bool solveT() {
    read();
    dijkstra(s - 1);
    return (dis == trueDis);
}

int main() {
    int t;
    for (fin >> t; t--;)
        fout << ((solveT()) ? "NU" : "DA") << newline;
    STOP
}