#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int infinit = std::numeric_limits<int>::max();

vector<int> Dijkstra(int noduri, int nodStart, vector<vector<pair<int, int>>> listaAdiacentaCuCosturi) {

    // initializare Dijkstra
    vector<int> distante(noduri + 1, infinit);
    vector<bool> vizitate(noduri + 1, false);

    // min-heap
    priority_queue<pair<int, int>, std::vector<pair<int, int>>, std::greater<>> minHeap;

    distante[nodStart] = 0;
    //vizitate[nodStart] = true;

    //punem nodul de start in heap
    minHeap.push({distante[nodStart], nodStart});

    while (!minHeap.empty()){
        //minimul din heap e in top
        pair<int, int> elementSiDistantaMin = minHeap.top();

        //dam pop pe priority queue imediat cum salvam top-ul
        minHeap.pop();

        // daca am trecut prin nodul din top, nu mai facem tot algoritmul pentru el
        if (vizitate[elementSiDistantaMin.second]){
            continue;
        }

        // vizitam un nod doar cand el ajunge in top-ul heap-ului
        vizitate[elementSiDistantaMin.second] = true;
        // pair.first -> distanta
        // pair.second -> nodul

        for( auto vecinSiCost : listaAdiacentaCuCosturi[elementSiDistantaMin.second]){
            // listaAdiacenta.first -> vecinul
            // listaAdiacenta.second -> costul muchiei nodCurent - vecin

            if(!vizitate[vecinSiCost.first]){
                // daca nu e vizitat, el nu e in arbore
                int distantaNouaVecin = distante[elementSiDistantaMin.second] + vecinSiCost.second;

                if (distantaNouaVecin < distante[vecinSiCost.first]){
                    distante[vecinSiCost.first] = distantaNouaVecin;
                    minHeap.push({distante[vecinSiCost.first], vecinSiCost.first});
                }
            }
        }
    }

    distante.erase(distante.begin());
    return distante;
}


int main() {
    ifstream in("distante.in");
    ofstream out("distante.out");

    int numarGrafuri, numarNoduri, numarMuchii, nodStart, extremitateInitiala, extremitateFinala, cost, numarBronzarel;

    vector<int> distanteMinimeDijkstra;
    vector<int> distanteMinimeBronzarel;

    in >> numarGrafuri;

    for(int i = 0; i < numarGrafuri; i++){
        in >> numarNoduri >> numarMuchii >> nodStart;

        vector<vector<pair<int, int>>> listaAdiacentaCuCosturi(numarNoduri + 1, vector<pair<int, int>>());

        for(int n = 0; n < numarNoduri; n++){
            in >> numarBronzarel;

            distanteMinimeBronzarel.push_back(numarBronzarel);
        }

        for(int m = 0; m < numarMuchii; m++){
            in >> extremitateInitiala >> extremitateFinala >> cost;

            listaAdiacentaCuCosturi[extremitateInitiala].push_back({extremitateFinala, cost});
            listaAdiacentaCuCosturi[extremitateFinala].push_back({extremitateInitiala, cost});
        }

        distanteMinimeDijkstra = Dijkstra(numarNoduri, nodStart, listaAdiacentaCuCosturi);

//        for(auto dist : distanteMinimeDijkstra){
//            cout << dist << " ";
//        }
//
//        cout << "Bronzarel \n";
//        for(auto dist : distanteMinimeBronzarel){
//            cout << dist << " ";
//        }
//
//        cout << "\n";

        bool egale = true;

        for(int k = 0; k < numarNoduri; k++){
            if(distanteMinimeBronzarel[k] != distanteMinimeDijkstra[k]){
                egale = false;
                break;
            }
        }

        if(egale){
            out << "DA\n";
        }
        else {
            out << "NU\n";
        }

//        if(distanteMinimeDijkstra == distanteMinimeBronzarel){
//            out << "DA\n";
//        }
//        else{
//            out << "NU\n";
//        }

        distanteMinimeBronzarel.clear();
        distanteMinimeDijkstra.clear();
    }

//    in.close();
//    out.close();

    return 0;
}