//TEF
 # include <fstream>
 # include <vector>
 # include <queue>
 
 # define dim 50005
 # define inf 999999999
 
 # define pb push_back
 
 using namespace std;
 
 ifstream f("distante.in");
 ofstream g("distante.out");
 
 struct distante
 {
	 int nod, cost;
 };
 
 queue < int > q;
 vector < int > drum( dim, inf ), ci( dim );
 vector < distante > a[ dim ];
 
 int n, m, t, inc;
 
 void afisare( int x );
 void rezolva( int x );
 void dijkstra( int x );
 
 void citire()
 {
	 int i, j;
	 int x, y, c;
	 
	 f >> t;
	 for ( i = 1 ; i <= t ; i++ )
	 {
		 f >> n >> m >> inc;
		 for ( j = 1 ; j <= n ; j++ )
			 f >> ci[ j ];
		 for ( j = 1 ; j <= m ; j++ )
		 {
			 f >> x >> y >> c;
			 a[ x ].pb( ( distante ) { y, c } );
			 a[ y ].pb( ( distante ) { x, c } );
		 }
		 rezolva( inc );
	 }
 }
 
 void rezolva( int x )
 {
	 int i, ok = 1;
	 
	 dijkstra( x );
	 
	 for ( i = 1 ; i <= n && ok == 1 ; i++ )
		 if ( drum[ i ] != ci[ i ] )
			 ok = 0;
		 afisare( ok );
	 
	 for ( i = 1 ; i <= n ; i++ )
	 {
		 a[ i ].clear();
		 drum[ i ] = inf;
	 }
 }
 
 void dijkstra( int x )
 {
	 int i, xx;
	 drum[ x ] = 0;
	 q.push( x );
	 
	 while( !q.empty() )
	 {
		 xx = q.front();
		 for ( i = 0 ; i < a[ xx ].size() ; i++ )
			 if ( drum[ a[ xx ][ i ].nod ] > drum[ xx ] + a[ xx ][ i ].cost )
			 {
				  drum[ a[ xx ][ i ].nod ] = drum[ xx ] + a[ xx ][ i ].cost;
				  q.push( a[ xx ][ i ].nod );
			 }
			 q.pop();
	 }
 }
 
 void afisare( int x )
 {
	 if( x == 0 )
		 g << "NU" << "\n";
	 else
		 g << "DA" << "\n";
 }
 
 int main()
 {
	 citire();
	 return 0;
 }