#include<cstdio>
using namespace std;

int t,i,j,n,m,s,sizeheap;
int d[50001],dcomp[50001],h[50001],poz[50001],viz[50001],minim;

struct lista {int nod; int cost; lista* next;};
lista* L[100001];

void add(int ind,int x, int y, int z)
{lista* q=new lista;
q->nod=y;
q->cost=z;
q->next=L[x];
L[x]=q;}

void swap(int x,int y)
{int aux=h[x];
h[x]=h[y];
h[y]=aux;
}

void swim(int x)
{int father;
 do{
 father=0;    
 if(x/2>=1)
    father=x/2;
 if(d[h[x]]<d[h[father]])
     {swap(x,father);
      poz[h[x]]=father;
      poz[h[father]]=x;}
 else 
    father=0;    
 x=father;        
 }while(father);
}

void sink(int x)
{int son;
do{son=0;
  if(2*x<=sizeheap)
    {son=2*x;
     if(2*x+1<=sizeheap && d[h[2*x+1]]<d[2*x])
       son++;}
  if(d[h[x]]>d[h[son]])   
     {poz[h[x]]=son;
      poz[h[son]]=x;
      swap(x,son);}
  else
    son=0;} while(son);   
}


int main()
{int gasit;
freopen("distante.in","r",stdin);
freopen("distante.out","w",stdout);
scanf("%d",&t);
int a,b,c;
for(i=0; i<t; i++)
{           


           
gasit=0;
scanf("%d %d %d",&n,&m,&s);
for(j=1; j<=n; j++)
  {scanf("%d",&dcomp[j]);
   L[j]=0;
   viz[j]=0;
   poz[j]=0;
   d[j]=1000000;}
for(j=1; j<=m; j++)  
  {scanf("%d %d %d",&a,&b,&c);
   add(i,a,b,c);
   add(i,b,a,c);}

sizeheap=1;
h[sizeheap]=s;
poz[s]=1;
d[s]=0;
for(j=1; j<=n; j++)
  printf("%d ",&L[j]);
printf("\n");  
while(sizeheap)
{lista* q=L[h[1]];
 viz[h[1]]=1;
 minim=d[h[1]];
 swap(1,sizeheap);
 poz[h[sizeheap]]=1;
 sizeheap--;
 sink(1);
 
 while(q)
 {if(viz[q->nod]==0)
 {if(poz[q->nod]==0)
      {sizeheap++;
       h[sizeheap]=q->nod;
       poz[q->nod]=sizeheap;
       d[q->nod]=minim+q->cost;
       swim(sizeheap);
       }
   else if(d[q->nod]>minim+q->cost) 
       {d[q->nod]=minim+q->cost;
        swim(poz[q->nod]);}
        }
  q=q->next;}
 
}

for(j=1; j<=n; j++)
 if(d[j]!=dcomp[j])
   {gasit=1;  break;}
if(gasit)
  printf("NU\n");
else
 printf("DA\n");
  

for(j=1; j<=n; j++)
 printf("%d ",d[j]);
printf("\n");

}

return 0;}