#include<iostream.h>
#include<fstream.h>
#include<iomanip.h>
long x1,t,n,m,s[50000],d[50000],p[50000],a[10000][10000],max=2000000,v[50000],j; 
fstream f,f1;
void citire()
{ int i,j,x,y,c;
  f>>n>>m>>x1;
  for (i=1;i<=n;i++) f>>v[i];
  for (i=1;i<=n;i++)
	  for (j=1;j<=n;j++)
		if (i!=j)  
			a[i][j]=max;
	    else a[i][j]=0;
 for (i=1;i<=m;i++)
	{f>>x>>y>>c; 
     a[x][y]=c;
	}
}


void dijkstra(int x)
{ int i,j,k,min;
  s[x]=1;
  p[x]=0;
  for (i=1;i<=n;i++)
   if (i!=x) { s[i]=0; d[i]=a[x][i];}
  for (i=1;i<=n;i++)
	if (i!=x && a[x][i]!=max) p[i]=x;
  for (i=1;i<=n-1;i++)
  { min=max;
    for (j=1;j<=n;j++)
		if (min>d[j] && s[j]==0) 
		{ min=d[j];k=j;}
	s[k]=1;
	for (j=1;j<=n;j++)
		if (s[j]==0 && d[j]>d[k]+a[k][j])
		{ d[j]=d[k]+a[k][j];
		  p[j]=k;
		}
  }
}

int main()
{ int i,j;
 f.open("distante.in",ios::in);	
f>>t;
f1.open("distante.out",ios::out);
for (i=1;i<=t;i++){
citire();

dijkstra(x1);


int ok=1;
  for (j=1;j<=n;j++)
	  if (v[j]!=d[j]) { ok=0; break;}
 if (ok==1) f1<<"DA"<<endl;
else f1<<"NU"<<endl;
}
f.close();
f1.close();
}