#include <fstream>
#include <set>
#include <vector>
#include <climits>
using namespace std;
ifstream f("distante.in");
   ofstream g("distante.out");
#define NMAX 50100
set< pair<int,int> > T;
vector <int> G[NMAX], C[NMAX];
long long int d[NMAX], corect[NMAX];
int S,k,m,n,p,i,a,b,c;
void dijkstra()
{   int i,x,val;
    for(i=1;i<=n;i++) d[i]=INT_MAX;
    d[p]=0;
    T.insert(make_pair(0,p));
    while(T.size()>0)
    {
        val=(*T.begin()).first;
        x=(*T.begin()).second;
        T.erase(*T.begin());
        for(i=0;i<G[x].size();i++)
            if(d[G[x][i]]>val+C[x][i])
               {d[G[x][i]]=val+C[x][i];
               T.insert(make_pair(d[G[x][i]],G[x][i]));
               }
    }
             for(i=1;i<=n;i++)
            g<<d[i]<<' ';
         g<<endl;

}
int verificare()
{
    for(i=1;i<=n;i++)
        if(d[i]!=corect[i])
            return 0;
    return 1;
}
int main()
{
   f>>S;
   for(k=1;k<=S;k++)
   {
       f>>n>>m>>p;
       for(i=1;i<=n;i++)
        f>>corect[i];
       for(i=1;i<=m;i++)
       {
           f>>a>>b>>c;
           G[a].push_back(b);
           G[b].push_back(a);
           C[a].push_back(c);
           C[b].push_back(c);
       }
       dijkstra();
       int ok;
       ok=verificare();
       if(ok) g<<"DA";
         else g<<"NU";
       for(i=1;i<=n;i++)
       {G[i].clear();
       C[i].clear();}
       g<<'\n';


   }

    return 0;
}