#include<stdio.h>
#define infile "distante.in"
#define outfile "distante.out"
#define nmax 50*1001
#define mmax 200*1001
#define inf ~(1<<31)
struct lista
	{
	int n,p,c; //nodul, pozitia si costul
	} l[mmax]; //lista
struct nod
	{
	int p,ph,c,cb; //pozitia, pozitia din heap, costul minim si costul minim gasit de bronzanel
	} n[nmax]; //nodurile
int h[nmax]; //min-heap-ul
int s,nrl,nrn,nrh;

//adauga arcul (x,y) cu costul c
void add(int m, int x, int y, int c)
	{
	l[m].n=y; l[m].c=c; l[m].p=n[x].p; n[x].p=m;
	}

void citire()
	{
	int i,x,y,c;
	scanf("%d %d %d",&nrn,&nrl,&s); //numarul de noduri, muchii si nodul de start
	for(i=1;i<=nrn;i++) scanf("%d",n[i].cb); //costurile lui Bronzanel
	for(i=1;i<=nrl;i++)
		{
		scanf("%d %d %d\n",&x,&y,&c); //(x,y) cu c
		add(2*i-1,x,y,c); //(x,y) cu c
		add(2*i,y,x,c); //(y,c) cu c
		}
	}

//adaugam nodul x in heap
void add_heap(int x)
	{
	int f=nrh,t=nrh/2; //fiul si tatal
	//nrh++; //facem loc in heap
	while(t) //cat timp are tata
		{
		if(n[h[t]].c>n[x].c) //tatal e mai mare
			{
			h[f]=h[t]; n[h[f]].ph=f; //coboram tatal peste fiu
			f=t; t=f/2; //refacem tatal si fiul
			}
		else t=0; //oprim cautarea
		}
	h[f]=x; n[h[f]].ph=f; //adaugam nodul in heap la pozitia corecta
	}

//combina nodul cu cei doi fi, a.i. sa refacem heap-ul
void comb_heap(int x)
	{
	int t=x,f=2*x; //tatal si fiul
	while(f<=nrh)
		{
		if(f<nrh&&n[h[f]].c>n[h[f+1]].c) f++; //e mai mic al doilea fiu
		if(n[h[f]].c<n[x].c)
			{
			h[t]=h[f]; n[h[t]].ph=t; //urcam copilul peste tatal
			t=f; f=2*t; //tatal si fiul
			}
		else f=nrh+1; //oprim cautarea
		}
	h[t]=x; n[h[t]].ph=t; //plasam la pozitia corecta
	}

//refac heap-ul din pozitia x (x e pozitia din heap)
void refac_heap(int x)
	{
	int f=x,t=x/2; //fiul si tatal
	x=h[x]; //punem acum in x nodul
	while(t) //cat timp are tata
		{
		if(n[h[t]].c>n[x].c) //tatal e mai mare
			{
			h[f]=h[t]; n[h[f]].ph=f; //coboram tatal peste fiu
			f=t; t=f/2; //refacem tatal si fiul
			}
		else t=0; //oprim cautarea
		}
	h[f]=x; n[h[f]].ph=f; //adaugam nodul in heap la pozitia corecta
	}

//extrage primul element din heap
int extrag_heap()
	{
	int v=h[1]; n[v].ph=-1; //nodul ce il scoatem
	h[1]=h[nrh--]; //punem ultimul element in locul lui
	comb_heap(h[1]); //refacem heap-ul
	return v; //returnam valoarea
	}

void initializare()
	{
	int ul;
	nrh=0; //heap-ul devine gol
	for(ul=1;ul<=nrn;ul++) n[ul].c=inf; //initial avem costul inifinit
	n[s].c=0; n[s].ph=-1; //la nodul sursa avem costul 0
	for(ul=n[s].p;ul;ul=l[ul].p) //trecem la copii lui s
		{
		n[l[ul].n].c=l[ul].c; //salvam costul cu care ajungem
		add_heap(l[ul].n); //il adaugam in heap
		}
	}

void dijktsra()
	{
	int x,ul;
	while(nrh) //cat timp avem noduri in heap
		{
		x=extrag_heap();
		for(ul=n[x].p;ul;ul=l[ul].p) //trecem la toti fii lui
			if(n[x].c+l[ul].c<n[l[ul].n].c) //ajungem cu un cost mai mic
				{
				n[l[ul].n].c=n[x].c+l[ul].c; //salvam noul cost
				if(!n[l[ul].n].ph) add_heap(l[ul].n); //nu este in heap...il adaugam
				else ; //refacem heap-ul dupa modificare
				}
		}
	}

int main()
{
int t;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

scanf("%d\n",&t); //numarul de teste
while(t--) //rezolvam testele
	{
	citire();
	if(n[s].cb) printf("NU"); //nodul de start trebuie sa aibe costul 0
	else
		{
		initializare();
		dijkstra(); //facem distanta minima
		}
	}

fclose(stdin);
fclose(stdout);
return 0;
}