/*
Alexandru Enache
Grupa 252
*/


#include <bits/stdc++.h>

using namespace std;

//ifstream fin("input"); ofstream fout("output");
ifstream fin("distante.in");ofstream fout("distante.out");


class Graph {

private:

    const int m_inf = 1e9;

    int m_nodes;
    vector<vector<int> > m_gr;
    vector<vector<pair<int, int> > > m_weighted_gr;
    vector<pair<int, pair<int, int> > > m_weighted_edges;
    vector<int> m_disjoint_parent, m_disjoint_cardinal;
    vector<vector<int> > m_capacity;
    vector<pair<pair<int, int>, bool> > m_edges;
    int m_bipartite_A, m_bipartite_B;


    void Dfs(int node, vector<bool> &used);

    void DfsBiconnectedComponents(int node, int parent, vector<int> &level, vector<int> &minimum_value, stack<int> &S,
                                  vector<vector<int> > &answer);

    void DfsStronglyConnectedComponents(int node, vector<vector<int> > &gr, vector<bool> &used, vector<int> &aux);

    void DfsSetLevel(int node, vector<int> &level);

    bool BfsMaxFlow(int source, int destination, vector<int> &parent, vector<vector<int> > &flow);

    int EulerNextNode(int node, pair<pair<int, int>, bool> &edge);

    int MaximumMatchingPropagation(int node, vector<int> &used, vector<int> &answer, vector<int> &matching);

public:

    Graph();

    Graph(int nodes, vector<vector<int> > &gr);

    Graph(int nodes, vector<vector<pair<int, int> > > &weighted_gr);

    Graph(int nodes, vector<pair<int, pair<int, int> > > &weighted_edges);

    Graph(int nodes, vector<vector<int> > &gr, vector<vector<int> > &capacity);

    Graph(int nodes, vector<vector<int> > &gr, vector<pair<pair<int, int>, bool> > &edges);

    Graph(int bipartite_A, int bipartite_B, vector<vector<int> > &gr);


    vector<int> Bfs(int start);

    int ConnectedComponents();

    vector<vector<int> > BiconnectedComponents();

    vector<vector<int> > StronglyConnectedComponents();

    vector<int> TopologicalOrder();

    bool HavelHakimi(vector<int> &v);

    int DisjointFindParent(int node);

    void DisjointUnite(int node_A, int node_B);

    vector<pair<int, pair<int, int> > > MinimumSpanningTree();

    vector<int> Dijkstra(int source);

    vector<int> BellmanFord(int source);

    int TreeDiameter();

    vector<vector<int> > RoyFloyd();

    int MaxFlow(int source, int destination);

    vector<int> EulerCycle();

    int MinCostHamiltonianCycle();

    vector<int> MaximumMatching();
};


//private

void Graph::Dfs(int node, vector<bool> &used) {
    used[node] = true;
    for (auto &x: m_gr[node]) {
        if (!used[x]) {
            Dfs(x, used);
        }
    }
}


void
Graph::DfsBiconnectedComponents(int node, int parent, vector<int> &level, vector<int> &minimum_value, stack<int> &S,
                                vector<vector<int> > &answer) {
    level[node] = level[parent] + 1;
    minimum_value[node] = level[node];
    S.push(node);
    for (auto &x : m_gr[node]) {
        if (level[x]) {
            if (x != parent) {
                minimum_value[node] = min(minimum_value[node], level[x]);
            }
        } else {
            DfsBiconnectedComponents(x, node, level, minimum_value, S, answer);
            minimum_value[node] = min(minimum_value[node], minimum_value[x]);
            if (minimum_value[x] >= level[node]) {
                vector<int> aux;
                while (S.top() != x) {
                    aux.push_back(S.top());
                    S.pop();
                }
                aux.push_back(x);
                S.pop();
                aux.push_back(node);
                answer.push_back(aux);
            }
        }
    }
}


void Graph::DfsStronglyConnectedComponents(int node, vector<vector<int> > &gr, vector<bool> &used, vector<int> &aux) {
    used[node] = true;
    for (auto &x : gr[node]) {
        if (!used[x]) {
            DfsStronglyConnectedComponents(x, gr, used, aux);
        }
    }
    aux.push_back(node);
}


void Graph::DfsSetLevel(int node, vector<int> &level) {
    for (auto &x: m_gr[node]) {
        if (!level[x]) {
            level[x] = level[node] + 1;
            DfsSetLevel(x, level);
        }
    }
}


bool Graph::BfsMaxFlow(int source, int destination, vector<int> &parent, vector<vector<int> > &flow) {
    for (int i = 1; i <= m_nodes; i++) {
        parent[i] = 0;
    }
    parent[source] = source;

    queue<int> Q;
    Q.push(source);
    int ok = 0;

    while (!Q.empty()) {
        int current_node = Q.front();
        Q.pop();
        if (current_node == destination) {
            ok = 1;
            continue;
        }
        for (auto &x : m_gr[current_node]) {
            if (!parent[x] && m_capacity[current_node][x] - flow[current_node][x] > 0) {
                parent[x] = current_node;
                Q.push(x);
            }
        }
    }
    return ok;
}


int Graph::EulerNextNode(int node, pair<pair<int, int>, bool> &edge) {
    edge.second = true;
    if (edge.first.first == node) {
        return edge.first.second;
    }
    return edge.first.first;
}


int Graph::MaximumMatchingPropagation(int node, vector<int> &used, vector<int> &answer, vector<int> &matching) {
    used[node] = 1;
    for (auto &x : m_gr[node]) {
        if (!matching[x] || (!used[matching[x]] && MaximumMatchingPropagation(matching[x], used, answer, matching))) {
            matching[x] = node;
            answer[node] = x;
            return 1;
        }
    }
    return 0;
}


//public

Graph::Graph() {
    m_nodes = 0;
    m_gr = {};

    m_disjoint_parent.resize(m_nodes + 1);
    m_disjoint_cardinal.resize(m_nodes + 1);

    for (int i = 1; i <= m_nodes; i++) {
        m_disjoint_parent[i] = i;
        m_disjoint_cardinal[i] = 1;
    }
}


//Unweighted Graph - Adjacency List
Graph::Graph(int nodes, vector<vector<int> > &gr) {
    m_nodes = nodes;
    m_gr = gr;

    m_disjoint_parent.resize(m_nodes + 1);
    m_disjoint_cardinal.resize(m_nodes + 1);

    for (int i = 1; i <= m_nodes; i++) {
        m_disjoint_parent[i] = i;
        m_disjoint_cardinal[i] = 1;
    }
}


//Weighted Graph - Adjacency List
Graph::Graph(int nodes, vector<vector<pair<int, int> > > &weighted_gr) {
    m_nodes = nodes;
    m_weighted_gr = weighted_gr;

    m_disjoint_parent.resize(m_nodes + 1);
    m_disjoint_cardinal.resize(m_nodes + 1);

    for (int i = 1; i <= m_nodes; i++) {
        m_disjoint_parent[i] = i;
        m_disjoint_cardinal[i] = 1;
    }
}


//Weighted Graph - List of Edges
Graph::Graph(int nodes, vector<pair<int, pair<int, int> > > &weighted_edges) {
    m_nodes = nodes;
    m_weighted_edges = weighted_edges;

    m_disjoint_parent.resize(m_nodes + 1);
    m_disjoint_cardinal.resize(m_nodes + 1);

    for (int i = 1; i <= m_nodes; i++) {
        m_disjoint_parent[i] = i;
        m_disjoint_cardinal[i] = 1;
    }
}


//Adjacency Matrix + Capacity
Graph::Graph(int nodes, vector<vector<int> > &gr, vector<vector<int> > &capacity) {
    m_nodes = nodes;
    m_gr = gr;
    m_capacity = capacity;

    m_disjoint_parent.resize(m_nodes + 1);
    m_disjoint_cardinal.resize(m_nodes + 1);

    for (int i = 1; i <= m_nodes; i++) {
        m_disjoint_parent[i] = i;
        m_disjoint_cardinal[i] = 1;
    }
}


//Adjacency List + List of Edges
Graph::Graph(int nodes, vector<vector<int> > &gr, vector<pair<pair<int, int>, bool> > &edges) {
    m_nodes = nodes;
    m_gr = gr;
    m_edges = edges;

    m_disjoint_parent.resize(m_nodes + 1);
    m_disjoint_cardinal.resize(m_nodes + 1);

    for (int i = 1; i <= m_nodes; i++) {
        m_disjoint_parent[i] = i;
        m_disjoint_cardinal[i] = 1;
    }
}


//Bipartite Graph
Graph::Graph(int bipartite_A, int bipartite_B, vector<vector<int> > &gr) {
    m_bipartite_A = bipartite_A;
    m_bipartite_B = bipartite_B;
    m_gr = gr;
}


vector<int> Graph::Bfs(int start) {
    queue<int> Q;
    vector<int> dist(m_nodes + 1, -1);

    dist[start] = 0;
    Q.push(start);

    while (!Q.empty()) {
        int current_node = Q.front();
        Q.pop();

        for (auto &x : m_gr[current_node]) {
            if (dist[x] == -1) {
                dist[x] = dist[current_node] + 1;
                Q.push(x);
            }
        }
    }

    return dist;
}


int Graph::ConnectedComponents() {
    int cont = 0;
    vector<bool> used(m_nodes + 1, false);
    for (int i = 1; i <= m_nodes; i++) {
        if (!used[i]) {
            Dfs(i, used);
            cont++;
        }
    }

    return cont;
}


vector<vector<int> > Graph::BiconnectedComponents() {
    vector<vector<int> > answer;

    vector<int> level(m_nodes + 1, 0);
    vector<int> minimum_value(m_nodes + 1, 0);
    stack<int> S;

    for (int i = 1; i <= m_nodes; i++) {
        if (!level[i]) {
            DfsBiconnectedComponents(i, 0, level, minimum_value, S, answer);
            while (!S.empty()) S.pop();
        }
    }

    return answer;
}


vector<vector<int> > Graph::StronglyConnectedComponents() {
    vector<vector<int> > answer;

    vector<bool> used(m_nodes + 1, false);
    vector<int> order;

    for (int i = 1; i <= m_nodes; i++) if (!used[i]) DfsStronglyConnectedComponents(i, m_gr, used, order);

    reverse(order.begin(), order.end());

    vector<vector<int> > gr_T(m_nodes + 1);

    for (int i = 1; i <= m_nodes; i++) {
        used[i] = false;
        for (auto &x : m_gr[i]) {
            gr_T[x].push_back(i);
        }
    }

    for (auto &x: order) {
        if (!used[x]) {
            vector<int> aux;
            DfsStronglyConnectedComponents(x, gr_T, used, aux);
            answer.push_back(aux);
        }
    }

    return answer;
}


vector<int> Graph::TopologicalOrder() {
    vector<bool> used(m_nodes + 1, false);
    vector<int> order;

    for (int i = 1; i <= m_nodes; i++)
        if (!used[i])
            DfsStronglyConnectedComponents(i, m_gr, used, order);

    reverse(order.begin(), order.end());

    return order;
}


bool Graph::HavelHakimi(vector<int> &v) {
    for (int i = 0; i < v.size(); i++) {
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());

        if (v[0] > (int) v.size() - 1)
            return false;

        for (int j = 1; j <= v[0]; j++) {
            v[j]--;
            if (v[j] < 0)
                return false;
        }
        v[0] = 0;
    }

    return true;
}


int Graph::DisjointFindParent(int node) {
    if (node != m_disjoint_parent[node]) {
        m_disjoint_parent[node] = DisjointFindParent(m_disjoint_parent[node]);
    }
    return m_disjoint_parent[node];
}


void Graph::DisjointUnite(int node_A, int node_B) {
    node_A = DisjointFindParent(node_A);
    node_B = DisjointFindParent(node_B);
    if (m_disjoint_cardinal[m_disjoint_parent[node_A]] > m_disjoint_cardinal[m_disjoint_parent[node_B]]) {
        int old_value = m_disjoint_cardinal[m_disjoint_parent[node_B]];
        m_disjoint_parent[node_B] = m_disjoint_parent[node_A];
        m_disjoint_cardinal[m_disjoint_parent[node_A]] += old_value;
    } else {
        int old_value = m_disjoint_cardinal[m_disjoint_parent[node_A]];
        m_disjoint_parent[node_A] = m_disjoint_parent[node_B];
        m_disjoint_cardinal[m_disjoint_parent[node_B]] += old_value;
    }
}


vector<pair<int, pair<int, int> > > Graph::MinimumSpanningTree() {
    vector<pair<int, pair<int, int> > > answer;

    sort(m_weighted_edges.begin(), m_weighted_edges.end());

    for (auto &x : m_weighted_edges) {
        if (DisjointFindParent(x.second.first) != DisjointFindParent(x.second.second)) {
            answer.push_back(x);
            DisjointUnite(x.second.first, x.second.second);
        }
    }

    return answer;
}


vector<int> Graph::Dijkstra(int source) {
    vector<int> dp(m_nodes + 1, m_inf);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> Q;
    vector<bool> used(m_nodes + 1, false);

    dp[source] = 0;
    Q.push({0, source});

    while (!Q.empty()) {
        pair<int, int> current_node = Q.top();
        Q.pop();
        if (used[current_node.second] || current_node.first != dp[current_node.second]) {
            continue;
        }
        used[current_node.second] = true;
        for (auto &x : m_weighted_gr[current_node.second]) {
            if (dp[x.first] > current_node.first + x.second) {
                dp[x.first] = current_node.first + x.second;
                Q.push({dp[x.first], x.first});
            }
        }
    }

    return dp;
}


vector<int> Graph::BellmanFord(int source) {
    vector<int> dp(m_nodes + 1, m_inf);

    queue<int> Q;
    vector<bool> used(m_nodes + 1, false);
    vector<int> frequency(m_nodes + 1, 0);

    dp[source] = 0;
    Q.push(source);

    while (!Q.empty()) {

        int current_node = Q.front();
        Q.pop();
        frequency[current_node]++;
        used[current_node] = false;

        if (frequency[current_node] > m_nodes) {
            return {};
        }

        for (auto &x : m_weighted_gr[current_node]) {
            if (dp[x.first] > dp[current_node] + x.second) {
                dp[x.first] = dp[current_node] + x.second;
                if (!used[x.first]) {
                    Q.push(x.first);
                    used[x.first] = true;
                } else {
                    frequency[x.first]++;
                }
            }
        }

    }

    return dp;
}


int Graph::TreeDiameter() {
    vector<int> level(m_nodes + 1, 0);
    level[1] = 1;
    DfsSetLevel(1, level);

    int maximum_value = 0;
    int position = 0;
    for (int i = 1; i <= m_nodes; i++) {
        if (maximum_value < level[i]) {
            maximum_value = level[i];
            position = i;
        }
    }

    for (auto &x : level) {
        x = 0;
    }
    level[position] = 1;
    DfsSetLevel(position, level);

    maximum_value = 0;
    for (int i = 1; i <= m_nodes; i++) {
        maximum_value = max(maximum_value, level[i]);
    }

    return maximum_value;
}


vector<vector<int> > Graph::RoyFloyd() {
    for (int k = 1; k <= m_nodes; k++) {
        for (int i = 1; i <= m_nodes; i++) {
            if (k == i || m_gr[i][k] == m_inf) {
                continue;
            }
            for (int j = 1; j <= m_nodes; j++) {
                if (i == j || m_gr[k][j] == m_inf) {
                    continue;
                }
                m_gr[i][j] = min(m_gr[i][j], m_gr[i][k] + m_gr[k][j]);
            }
        }
    }
    return m_gr;
}


int Graph::MaxFlow(int source, int destination) {
    int answer = 0;

    vector<int> parent(m_nodes + 1, 0);
    vector<vector<int> > flow(m_nodes + 1);
    for (auto &x: flow) {
        x.resize(m_nodes + 1, 0);
    }

    while (BfsMaxFlow(source, destination, parent, flow)) {
        for (auto &x : m_gr[destination]) {
            if (!parent[x]) {
                continue;
            }
            parent[destination] = x;
            int current_node = destination;
            int minimum_value = m_inf;
            while (current_node != source) {
                minimum_value = min(minimum_value, m_capacity[parent[current_node]][current_node] - flow[parent[current_node]][current_node]);
                current_node = parent[current_node];
            }
            current_node = destination;
            while (current_node != source) {
                flow[parent[current_node]][current_node] += minimum_value;
                flow[current_node][parent[current_node]] -= minimum_value;
                current_node = parent[current_node];
            }
            answer += minimum_value;
        }
    }

    return answer;
}

vector<int> Graph::EulerCycle() {
    vector<int> position(m_nodes + 1, -1);
    vector<int> answer;

    for (int i = 1; i <= m_nodes; i++) {
        if (m_gr[i].size() % 2) {
            return answer;
        }
    }

    stack<int> S;

    S.push(1);

    while (!S.empty()) {
        int node = S.top();
        int ok = 1;
        while (position[node] + 1 < (int) m_gr[node].size()) {
            position[node]++;
            if (!m_edges[m_gr[node][position[node]]].second) {
                S.push(EulerNextNode(node, m_edges[m_gr[node][position[node]]]));
                ok = 0;
                break;
            }
        }
        if (ok) {
            S.pop();
            answer.push_back(node);
        }
    }

    answer.pop_back();

    if (answer.size() != m_edges.size()) {
        answer.clear();
    }

    return answer;

}

int Graph::MinCostHamiltonianCycle() {
    vector<vector<int> > bit_masks_with_i_number_of_bits(m_nodes + 1);
    vector<vector<int> > dp((1 << m_nodes));

    for (auto &x : dp) {
        x.resize(m_nodes + 1, 0);
    }

    for (int bit_mask = 0; bit_mask < (1 << m_nodes); bit_mask++) {
        int cont = 0;
        for (int bit = 0; bit < m_nodes; bit++) {
            if (bit_mask & (1 << bit)) {
                cont++;
            }
        }
        bit_masks_with_i_number_of_bits[cont].push_back(bit_mask);
    }

    for (int i = 1; i <= m_nodes; i++) {
        for (auto &x : bit_masks_with_i_number_of_bits[i]) {
            for (int l = 0; l < m_nodes; l++) {
                if (dp[x][l] != 0 || (x == 1 && l == 0)) {
                    for (int bit = 0; bit < m_nodes; bit++) {
                        if ((!(x & (1 << bit))) && m_gr[l][bit] != 0) {
                            if (dp[x + (1 << bit)][bit] == 0) {
                                dp[x + (1 << bit)][bit] = dp[x][l] + m_gr[l][bit];
                            } else {
                                dp[x + (1 << bit)][bit] = min(dp[x + (1 << bit)][bit], dp[x][l] + m_gr[l][bit]);
                            }
                        }
                    }
                }
            }
        }
    }

    int minimum_value = m_inf;
    for (int l = 0; l < m_nodes; l++) {
        if (dp[(1 << m_nodes) - 1][l] != 0 && m_gr[l][0] != 0) {
            minimum_value = min(minimum_value, dp[(1 << m_nodes) - 1][l] + m_gr[l][0]);
        }
    }

    return minimum_value;
}

vector<int> Graph::MaximumMatching() {
    vector<int> used(m_bipartite_A + 1);
    vector<int> answer(m_bipartite_A + 1);
    vector<int> matching(m_bipartite_B + 1);

    int c = 1;
    while (c) {
        c = 0;
        for (int i = 1; i <= m_bipartite_A; i++) {
            used[i] = 0;
        }
        for (int i = 1; i <= m_bipartite_A; i++) {
            if (!answer[i] && !used[i]) {
                c |= MaximumMatchingPropagation(i, used, answer, matching);
            }
        }
    }

    return answer;
}




void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tests;
    fin >> tests;

    while (tests--){
        int n, m, source;
        fin >> n >> m >> source;

        vector < int > expected_answer(n + 1);
        vector< vector < pair <int, int> > > gr(n + 1);

        for (int i=1; i<=n; i++){
            fin>>expected_answer[i];
        }

        for (int i = 1; i <= m; i++) {
            int a, b, value;
            fin >> a >> b >> value;
            gr[a].push_back({b, value});
            gr[b].push_back({a, value});
        }

        Graph graph = Graph(n, gr);

        vector < int > answer = graph.Dijkstra(source);

        bool ok = true;
        for (int i=1; i<=n; i++){
            if (answer[i] != expected_answer[i]){
                ok = false;
            }
        }

        if (ok)
            fout<<"DA\n";
        else
            fout<<"NU\n";

    }

}


int main() {

    solve();

    return 0;
}