#include <fstream>
#include <set>
#include <vector>
#define nmax 50005
#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);
        ld[j].push_back(i);
        lc[i].push_back(c);
        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() == 0 )
     {
         int i, c;
       i = dij.begin()->first;
       c = dij.begin()->second;
      dij.erase(dij.begin());
      for ( int k = 0 ; k < ld[i].size() ; k ++ )
       {
           int ii, jj;
           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]));
           }
       }
     }
}

void solve()
{
    void dijk();
     ok = false;
     for (int  i = 1 ;  i <= n && ok == false ; i++ )
    {
        if( dist_calc[i] != dist[i] && dist[i] != INF )
        ok = true;
     else
        ok = false;
       }
        if( ok == true )
     g<< "NU\n";
     else
        g << "DA\n";

}

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