#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

ifstream in("distante.in");
ofstream out("distante.out");

struct muchie{
	int v,cost;
};

int t,n,m,s,p,u;
const int INF=1<<30;
const int N=1<<17;
vector <muchie> a[N];
int d[N],rez[N],coada[10*N];

void scrie(int v[N])
{
	for(int i=1 ; i<=n ; ++i)
		cout<<v[i]<<" ";
	cout<<"\n";
}

void BFord(){
	int x,y,i;
	p=1;
	u=1;
	coada[u]=s;
	while(p<=u){
		x=coada[p++];
		//cout<<"scot "<<x<<"\n";
		for(i=0;i<a[x].size();i++){
			y = a[x][i].v;
			if(rez[y]<=rez[x]+a[x][i].cost)
				continue;
			rez[y]=rez[x]+a[x][i].cost;
			u++;
			coada[u]=y;
			//cout<<"adaug "<<y<<"\n";
		}
	}
	scrie(rez);
	for(i=1;i<=n;i++){
		if(d[i]!=rez[i]){
			out<<"NU\n";
			return;
		}
	}
	out<<"DA\n";
}

void prelucrare(){
	int i;
	for(i=1;i<=n;i++){
		rez[i]=INF;
	}
	rez[s]=0;
	BFord();
}

void citire(){
	int i,x,y,c,j;
	muchie aux;
	in>>t;
	for(j=1;j<=t;j++){
		in>>n>>m>>s;
		//cout<<"am citit "<<n<<" "<<m<<" "<<s<<"\n";
		for(i=1;i<=n;i++){
			in>>d[i];
		}
		scrie(d);
		for(i=1;i<=m;i++){
			in>>x>>y>>c;
			//cout<<"x: "<<x<<"y: "<<y<<"c: "<<c<<"\n";
			aux.v=y;
			aux.cost=c;
			a[x].push_back(aux);
			aux.v=x;
			a[y].push_back(aux);
		}
		prelucrare();
		for(i=1 ; i<=n ; ++i)
			a[i].clear();
	}
}

int main(){
	citire();
	return 0;
}