#include<fstream.h>
#include<iostream.h>

int viz[51000],m,n,t,s,sol[51000],a[101000],b[101000],c[101000],da,gasit,i,j;

int main()
{
	ifstream f("distante.in");
	ofstream g("distante.out");
	f>>t;
	for(j=1;j<=t;j++)
	{
		f>>n>>m>>s;
		for(i=1;i<=n;i++)
			f>>sol[i];
		for(i=1;i<=m;i++)
			f>>a[i]>>b[i]>>c[i];
		da=1;
		if(sol[s])
			da=0;
		for(i=1;i<=n;i++)
			viz[i]=0;
		for(i=1;i<=m&&da;i++)
		{
			if(sol[a[i]]==sol[b[i]]+c[i])
				viz[a[i]]=1;
			else
				if(sol[a[i]]>sol[b[i]]+c[i])
					da=0;
			if(sol[b[i]]==sol[a[i]]+c[i])
				viz[b[i]]=1;
			else 
				if(sol[b[i]]>sol[a[i]]+c[i])
					da=0;
		}
		for(i=1;i<=n;i++)cout<<viz[i]<<' ';
		cout<<endl;
		gasit=0;
		for(i=1;i<=n&&!gasit;i++)
			if(!viz[i]&&i!=s)gasit=1;
		if(gasit)
			da=0;
		if(da)
			g<<"DA\n";
		else 
			g<<"NU\n";
	}
	return 0;
}