#include <fstream>
#include <vector>
#include <set>
#include <cstring>
#define INF 1e9
#define Nmax 50005

using namespace std;

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

int t;
int n, m, s, dist_calc[Nmax], dist[Nmax];
vector <int> ld[Nmax], lc[Nmax];
set <pair <int, int > > dij;
set <pair <int, int > > ::iterator w;

void read()
{
    f >> n >> m >> s;
    for ( int i = 1 ; i <= n ; i ++ )
        f >> dist_calc[i];
    for (;m;m--)
     {int i,j,c;
         f >> i >> j >> c;
         ld[i].push_back(j);
         lc[i].push_back(c);
         ld[j].push_back(i);
         lc[j].push_back(c);
     }
}

void dijk()
{
    for ( int i = 1 ; i <= n ; i ++ )
     dist[i]=INF;
     dist[s]=0;
    dij.insert(make_pair(s,0));
     while(!dij.empty())
      {
          int i = dij.begin()->first;
          int c = dij.begin()->second;
           dij.erase(dij.begin());
           for ( int k = 0 ; k < ld[i].size(); k ++ )
            {
                int ii = ld[i][k];
                 if(dist[i]+lc[i][k] < dist[ii])
                 {
                     w=dij.find(make_pair(ii,dist[ii]));
                      if(w!=dij.end())
                       dij.erase(w);
                    dist[ii]=dist[i]+lc[i][k];
                    dij.insert(make_pair(ii,dist[ii]));
                 }
            }
      }
    bool ok=false;
    for ( int i = 1 ; i <= n && ok ==  false ; i ++ )
      if(dist_calc[i]!=dist[i]&&dist[i]!=INF)
        ok=true;
    if(ok == true )
      g << "NU\n";
     else
      g << "DA\n";
}
void empt()
{
    for ( int i = 1 ; i <= n ; i ++ )
      {
          while(!lc[i].empty())
           {
               lc[i].pop_back();
               ld[i].pop_back();
           }
      }
      memset(dist_calc,0,sizeof(dist_calc));
}
void solve()
{
    empt();
    read();
    dijk();
}

int main()
{
    f >> t;
     while ( t -- )
     {
         solve();
     }
    return 0;
}