#include <fstream>
#include <set>
#include <vector>
#define nmax 500005
#define INF 1e12

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

int t, n, m, s, dist_calc[nmax], dist[nmax];
bool ok = 0;
set <pair <int, int > > dij;
set <pair <int, int > > ::iterator w;
vector < int > lc[nmax], ld[nmax];
void dijk()
{
        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);
     }

    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]));
                 }
            }
      }
      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 solve()
{
    dijk();
}
int main()
{
    f >> t;
    while ( t-- )
    {
        solve();
    }
    return 0;
}