/// DISTANTE
#include<fstream>
#include<vector>
#include<queue>
#include<limits>

using namespace std;

typedef pair<unsigned, unsigned> NODE;
typedef vector<NODE> V_NODE;
typedef numeric_limits<unsigned> U_LIM;

ifstream inStr("distante.in");

class Graph {
private:
    vector<V_NODE> adjList;
    vector<unsigned> dist, myDist;
    unsigned numNodes, numArcs, dijkSource;
public:
    Graph();
    void dijkstra();
    bool correct() {return (dist == myDist);}
};

Graph::Graph() {
    inStr >> numNodes >> numArcs >> dijkSource;
    dijkSource--;
    dist.resize(numNodes);
    adjList.resize(numNodes);
    for(unsigned i = 0; i < numNodes; i++)
        inStr >> dist[i];

    unsigned from, to, cost;
    for(unsigned i = 0; i < numArcs; i++) {
        inStr >> from >> to >> cost;
        adjList[from-1].push_back(NODE(cost, to-1));
        adjList[to-1].push_back(NODE(cost, from-1));
    }
}

void Graph::dijkstra() {
    priority_queue<NODE, V_NODE, greater<NODE> > nodes;
    myDist.assign(numNodes, U_LIM::max());
    unsigned current, currNeigh, currDist, alt;
    myDist[dijkSource] = 0;
    nodes.push(NODE(myDist[dijkSource], dijkSource));

    while(!nodes.empty()) {
        if(nodes.top().first != myDist[nodes.top().second])
            nodes.pop();

        current = nodes.top().second;
        nodes.pop();

        for(V_NODE::iterator it = adjList[current].begin(); it != adjList[current].end(); it++) {
            currNeigh = it->second;
            currDist = it->first;

            alt = myDist[current] + currDist;
            if(alt < myDist[currNeigh]) {
                myDist[currNeigh] = alt;
                nodes.push(NODE(myDist[currNeigh], currNeigh));
            }
        }
    }
}

int main() {
    ofstream outStr("distante.out");

    int T;
    inStr >> T;
    Graph *graph;

    for(int i = 0; i < T; i++) {
        graph = new Graph();
        graph->dijkstra();
        if(graph->correct())
            outStr << "DA\n";
        else
            outStr << "NU\n";
        delete graph;
    }

    return 0;
}