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

using namespace std;

vector < int > Dijkstra(int nod_pornire, int n, vector < vector < pair < int,int > > > lista_vecini){
    priority_queue < pair < int, int >, vector < pair <int, int> >, greater < pair < int, int > > > coada_prioritati;
    vector < int > distante(n+1, 999999);
    vector < bool > apartine_Coada(n+1, 0);
    coada_prioritati.push(make_pair(0,nod_pornire));
    distante[nod_pornire] = 0;
    while( coada_prioritati.size() != 0 ){
        int x = coada_prioritati.top().second;
        coada_prioritati.pop();
        if( apartine_Coada[x] ){
            continue;
        }

        apartine_Coada[x] = 1;
        for( int i = 1; i < lista_vecini[x].size(); i++ ){

            if( !apartine_Coada[lista_vecini[x][i].first ] ){
                if( distante[ lista_vecini[x][i].first ] > distante[x] + lista_vecini[x][i].second ){
                    distante[ lista_vecini[x][i].first ] = distante[x] + lista_vecini[x][i].second;
                    coada_prioritati.push(make_pair(distante[lista_vecini[x][i].first ], lista_vecini[x][i].first));
                }
            }
        }
    }
    return distante;
}

int main(){
    int t;
    ifstream fin("distante.in");
    ofstream fout("distante.out");
    fin >> t;
    for( int z = 0; z < t; z++ ){
        int n,m;
        vector < vector < pair < int,int > > > lista_vecini;
        int start;
        fin >> n >> m >> start;
        vector < int > solutie;
        solutie.push_back(999999);
        for( int i = 0; i < n; i++ ){
            int nr;
            fin >> nr;
            if( nr == 0 ) solutie.push_back(999999);
            else solutie.push_back(nr);
        }
        int intrare, iesire, cost;
        vector < pair < int, int > > v(1,make_pair(-1,-1));
        for( int i = 0; i <= n+1; i++ ){
            lista_vecini.push_back(v);
        }
        for( int i = 1; i <= m; i++ ){
            fin >> intrare >> iesire >> cost;
            lista_vecini[intrare].push_back(make_pair(iesire,cost));
            lista_vecini[iesire].push_back(make_pair(intrare,cost));
        }
        solutie[start] = 0;
        vector < int> distante = Dijkstra(start,n,lista_vecini);
        if( solutie == distante ) fout << "DA" << '\n';
        else fout << "NU" << '\n';
    }
    return 0;
}