#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
using namespace std;
const int INF=1e9;
int viz[50001];
typedef struct
{
    int a,b,c;
}muchie;
struct cmp {
    bool operator()(const pair<int,int> &leeft, const pair<int,int> &rieght) {
        return leeft.second < rieght.second;
    }
};
vector<int> Dijkstra(vector <pair<int,int> > v[50001],int N,int M,int nod_start)
{
   // sort(v.begin(),v.end(),cmp);
    vector<int> d;
    //cout<<"DA";
    int i,counter=N;
    vector<int> tata;
    for(i=1;i<=N;i++)
    {
        d[i-1]=INF;
        viz[i-1]=0;
       // tata[i-1]=0;
    }
    d[nod_start]=0;
    int index=1,nod;
    //cout<<"DA";
    queue<int> Q;
    viz[nod_start]=1;
    Q.push(nod_start);
    while(!Q.empty())
    {
        int nod;
        nod=Q.front();
        viz[nod]=0;
        Q.pop();
        for(int j=0;j<v[nod].size();j++)
        {
            if(d[nod]+v[nod][j].second<d[v[nod][j].first])
            {
                d[v[nod][j].first]=d[nod]+v[nod][j].second;
                if(viz[v[nod][j].first]==0)
             {
                 //tata[v[nod][j].first]=nod;
                Q.push(v[nod][j].first);
                viz[v[nod][j].first]=1;
            }
            }
        }
       // counter--;
    }
    return d;
}
int comparare(vector<int> a,vector<int> b,int N)
{
    for(int i=0;i<=N-1;i++)
    {
        if(a[i]!=b[i])
        {
            return 0;
        }
    }
    return 1;
}
int main()
{

    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    int index,T;
    fin>>T;
   // cout<<"DA";
    for(index=1;index<=T;index++)
    {
    vector < pair<int,int> > v[50001];
   // cout<<v[0].first<<' '<<v[0].second;
    int N,M,S,i,j,q;
    fin>>N>>M>>S;
    vector<int> dist,new_dist;
    for(i=1;i<=N;i++)
    {
        fin>>q;
        dist.push_back(q);
    }
    for(i=1;i<=M;i++)
    {
        muchie x;
        fin>>x.a>>x.b>>x.c;
        //cout<<"DA";
        v[x.a].push_back(make_pair(x.b,x.c));
        v[x.b].push_back(make_pair(x.a,x.c));
    }
    new_dist=Dijkstra(v,N,M,S);
    if(comparare(dist,new_dist,N)==1)
    {
        fout<<"DA";
    }
    else
    {
        fout<<"NU";
    }
    fout<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}