#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#define inf (1<<30)
#define value first
#define node second
#define nmax 50001
using namespace std;

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

int n, m, source_node;
int initial[nmax],  best[nmax];

void read_data(vector< pair<int, int> > v[nmax]){
    int x, y, weight, i;
    fin >> n >> m >> source_node;
    for(i=1; i<=n; i++) fin >> initial[i];
    for(i=1; i<=m; i++){
        fin >> x >> y >> weight;
        v[x].push_back(make_pair(weight, y));
    }

}

void dijkstra(vector< pair<int, int> > v[nmax], set< pair<int, int> > s){
    s.insert(make_pair(0, source_node));
    while(!s.empty()){
        int cur= s.begin() -> node;
        int cur_val= s.begin() -> value;
        for(int i=0; i<v[cur].size();  i++){
            int neigh= v[cur][i].node;
            int neigh_val= v[cur][i].value;
            if(best[neigh] > best[cur] + neigh_val){
                best[neigh] = best[cur] + neigh_val;
                s.insert(make_pair(best[neigh], neigh));
            }
       }
       s.erase(s.begin());
    }
}

void second_main(){
    vector< pair<int, int> > v[nmax];
    set< pair<int, int > > s;
    bool ok;

    read_data(v);

    for(int i=1; i<=n; i++) best[i]= inf;
    best[source_node]= 0;

    dijkstra(v, s);

    for(int i=1; i<=n; i++) if(best[i] != initial[i]) ok= true;
    if(!ok) fout << "DA\n";
    else fout << "NU\n";
    for(int i=1; i<=n; i++) best[i]= inf;
    for(int i=1; i<=n; i++)   v[i].clear();

}


int main(){
    int graphs_number;
    fin >> graphs_number;
    while(graphs_number!=0){
        graphs_number--;
        second_main();
    }
    return 0;
}