#include <fstream>
#include <vector>
#include <queue>
#include <sstream>
#include <cstring>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define dim 50001
#define inf 0x3f3f3f3f
using namespace std;
 
struct  comp{
    bool operator() (const pii &a,const pii &b)
    {
        return a.y>b.y;
    }
};
 
 
priority_queue <pii,vector<pii>,comp > H;
vector <pii> v[dim];
 
int m,n,s,dist[dim];
string db,cr;
 
ifstream f("distante.in");
ofstream g("distante.out");
 

void read(){
     
 
	for(int i = 1; i <= n; i++){
		v[i].clear();
    	}

    	int a,b,c;
   	
	f >> n >> m >> s;
	f.get();
	getline(f,db);	

	for(int i = 1; i <= m; i++){
		f >> a >> b >> c;
		v[a].pb(mp(b,c));
		v[b].pb(mp(a,c));
    	}
}
 
 
void Dijkstra(){
     
   	 int u,d,newd;
   	 memset(dist,inf,sizeof(dist));
   	 dist[s] = 0;
 
	H.push(mp(s,0));
	while(!H.empty()){
		u=H.top().x;
		d=H.top().y;
      		H.pop();
       		for(int i = 0; i < int(v[u].size()); i++){
			newd = d + v[u][i].y;
           		if(newd < dist[v[u][i].x]){
               			dist[v[u][i].x] = newd;
              			H.push(mp(v[u][i].x,newd));
            		}
        	}
    	}
}


inline bool verif(){

	
	stringstream ss;
	ss << dist[1];
	for(int i = 2; i <= n; i++){
		 ss << " ";
		 ss <<  dist[i];
	}
	cr = ss.str();
	if(cr == db) return 1;
	return 0;
}

 
int main(){
     
	int t;
 	f >> t;
  	for(int i = 1; i <= t; i++){
		read(); 
		Dijkstra();
        	g << ((verif())?"DA\n":"NU\n");
    	}  
}