#include <bits/stdc++.h>

using namespace std;

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

const int maxNodes = 1e5+5;

const int infinite = 1<<30;

int totalTests, totalNodes, totalEdges, startNode;

int givenDistances[maxNodes],
    realDistances[maxNodes];

vector <pair <int, int> > edges[maxNodes];

priority_queue <pair <int, int> > orderedQueue;

bitset <maxNodes> visited;

inline void readVariables(){
    fin >> totalNodes >> totalEdges >> startNode;

    for ( int index = 1; index <= totalNodes; index++ )
        fin >> givenDistances[index];

    int origin, destiantion, cost;
    for ( int index = 1; index <= totalEdges; index++ ){
        fin >> origin >> destiantion >> cost;
        edges[origin].push_back({destiantion, cost});
    }
}

inline void determinateDistances(){
    for ( int index = 1; index <= totalNodes; index++ )
        realDistances[index] = infinite;
    realDistances[startNode] = 0;
    orderedQueue.push({0,startNode});

    int currentNode, currentCost;
    for ( ; orderedQueue.size(); ){
        tie(currentCost, currentNode) = orderedQueue.top();
        orderedQueue.pop();
        currentCost *= -1;

        if ( visited[currentNode] )
            continue;

        visited[currentNode] = true;

        for ( auto nextNode : edges[currentNode] ){
            if ( realDistances[nextNode.first] > currentCost + nextNode.second ){
                realDistances[nextNode.first] = currentCost + nextNode.second;
                orderedQueue.push({-realDistances[nextNode.first], nextNode.first});
            }
        }
    }
}

inline void checkAnswers(){
    bool okay = true;
    for ( int index = 1; index <= totalNodes; index++ )
        if ( realDistances[index] != givenDistances[index] )
            okay = false;

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

inline void resetVariables(){
    for ( int index = 0; index < totalNodes; index++ )
        edges[index].clear();

    for ( ; orderedQueue.size(); orderedQueue.pop() );

    visited.reset();
    memset(givenDistances,0,totalNodes+1);
    memset(realDistances,0,totalNodes+1);
}

int main(){
    fin >> totalTests;
    for ( ; totalTests; totalTests-- ){
        readVariables();
        determinateDistances();
        checkAnswers();
        resetVariables();
    }
    return 0;
}