#include <fstream>
#include <vector>
#include <queue>
#define inf 50000000
using namespace std;

 struct nod{
 int val,nodv;
 }temp;

    ifstream f("distante.in");
    ofstream g("distante.out");

 int n,m,t,s,xs,ys,c;
 vector <vector < nod > > graf;
 vector < int > Cost;
 queue < int > q;
 vector < int > V;

 void citire(){

for(int i=1;i<=n;i++)
    f >> V[i];
graf.resize(n+1);

    for(int i=1;i<=m;i++){
        f >> xs >> ys >> c;
        temp.val = c;
        temp.nodv = ys;
        graf[xs].push_back(temp);
}}


 void Dijkstra(){

int first  = s;
q.push(s);
Cost[s] = 0;
Cost.resize(n+1,inf);

    while(!q.empty()){
        for(vector < nod > :: iterator it = graf[first].begin();it!=graf[first].end();it++ ){
            if(Cost[it->nodv] > Cost[first] + it-> val){
               Cost[it->nodv] = Cost[first] + it-> val;
                q.push(it->nodv);
            }
        }
    q.pop();
    first = q.front();


    }
}

void afiseaza(){

int gasit = 1;
    for(int i =1;i<=n;i++)
    if(V[i]!=Cost[i])
        gasit = 0;

    if(!gasit)
        g << "NU" << '\n';
        else g << "DA" << '\n';
}

int main(){

    f >> t;
    f >> n >> m >> s;

for(int k=1;k<=t;k++){

    citire();
    Dijkstra();
    afiseaza();
    graf.clear();
    Cost.clear();
    V.clear();
}

f.close();
g.close();
return 0;
}