#include<fstream>
#include<vector>
#define inf 1000000
using namespace std;
int n,m,i,j,nrt,start,q[100001],c,x,y,d[50001],a[50001];
vector<int> g1[50001],g2[50001];
int st,dr,p;
int main()
{
	ifstream f("distante.in");
	ofstream g("distante.out");
	f>>nrt;
	while(nrt--)
	{
		f>>n>>m>>start;
		for(i=1;i<=n;i++)
		{
			f>>a[i];
			d[i]=inf;
			g1[i].clear();
			g2[i].clear();
			g1[i].push_back(0);
			g2[i].push_back(0);
		}
		for(i=1;i<=m;i++)
		{
			f>>x>>y>>c;
			g1[x].push_back(y);
			g1[y].push_back(x);
			g2[x].push_back(c);
			g2[y].push_back(c);
			
		}
		d[start]=0;
		q[1]=start;
		st=dr=1;
		while(st<=dr)
		{
			p=q[st++];
			for(i=1;i<g1[p].size();i++)
				if(d[g1[p][i]]>d[p]+g2[p][i])
				{
					d[g1[p][i]]=d[p]+g2[p][i];
					q[++dr]=g1[p][i];
				}
		}
	
		int ok=1;
		i=0;
		while(ok&&i<n)
		{
			++i;
			if(a[i]!=d[i])
				ok=0;
		}
		
		
		for(i=1;i<=n;++i)
			g<<d[i]<<" ";
		g<<"\n";
		
		if(ok)
			g<<"DA\n";
		else
			g<<"NU\n";
	}
	return 0;
}