#include<iostream.h>
#include<fstream.h>
int i,j,k,n,m,t,s,ok=1;
long d[50001],r[50001],a[100001][4];
int main()
{ifstream f("dijkstra.in");
ofstream h("dijkstra.out");
    f>>t;
for(k=1;k<=t;k++)
{
    f>>n>>m>>s;
for(i=1;i<=n;i++)
f>>r[i];
for(i=1;i<=n;i++)
        d[i]=2000001;
for(i=1;i<=m;i++)
        {f>>a[i][1]>>a[i][2]>>a[i][3];
          if(a[i][1]==s)d[a[i][2]]=a[i][3];
          else if(a[i][2]==s)d[a[i][1]]=a[i][3];}
 
d[s]=0;
 ok=1;
 while(ok==1)
{  ok=0;
for(k=1;k<=m;k++)
         if(d[a[k][2]] > d[a[k][1]] + a[k][3])
                                 {d[a[k][2]]=d[a[k][1]]+a[k][3];
                                  ok=1;}
}
for(i=1;i<=n;i++)
     {if(d[i]==r[i])  h<<"DA"<<endl;
       else  h<<d[i]<<"NU"<<endl;}
}
return 0;
}