#include <bits/stdc++.h>
using namespace std;

const int NMAX = 5e4 + 10;

int distances[NMAX], result[NMAX];
vector<pair<int, int>> adj[NMAX];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> hp;


void read_input(int &n, int &m, int &s) {
    scanf("%d %d %d", &n, &m, &s);
    for (int i = 1; i <= n; i++)
        scanf("%d", &distances[i]);
    for (int i = 1; i <= m; i++) {
        int x, y, cost; scanf("%d %d %d", &x, &y, &cost);
        adj[x].push_back({cost, y});
        adj[y].push_back({cost, x});
    }
}
void clear_structures(const int &n) {
    for (int i = 1; i <= n; i++)
        adj[i].clear();
}
bool check_correct(const int &n) {
    for (int i = 1; i <= n; i++) {
        if (distances[i] != result[i]) return false;
    }
    return true;
}
void print_output(const int &n) {
    printf(check_correct(n) ? "DA\n" : "NU\n");
}
void expand(pair<int, int> current_node) {
    for (auto son : adj[current_node.second]) {
        int current_cost = current_node.first + son.first;
        if (result[son.second] > current_cost) {
            result[son.second] = current_cost;
            hp.push(son);
        }
    }
}

void dijkstra(const int &start_node, const int &n) {
    for (int i = 1; i <= n; i++) result[i] = INT_MAX;
    result[start_node] = 0;
    hp.push({0, start_node});
    while (!hp.empty()) {
        pair<int, int> top_node = hp.top();
        hp.pop();
        if (top_node.first != result[top_node.second]) continue;
        expand(top_node);
    }
}

void solve_case() {
    int n, m, s;
    read_input(n, m, s);
    dijkstra(s, n);
    print_output(n);
    clear_structures(n);
}
int main() {
    freopen("distante.in", "r", stdin);
    freopen("distante.out", "w", stdout);

    int t; scanf("%d", &t);
    for (; t > 0; t--) {
        solve_case();
    }
    return 0;
}