#include <bits/stdc++.h>
#define lim 50005
using namespace std;

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

int oo=100000000;
long long n, m, s, t, d[lim], inq[lim], r[lim];
struct comp
{
    bool operator()(int x, int y)
    {
        return d[x]>d[y];
    }
};
priority_queue <int, vector <int>, comp > q;
vector <pair <int, int> > v[lim];

void solve()
{
    d[s]=0;
    q.push(s);
    int a;
    while(!q.empty())
    {
        a=q.top();
        for(int i=0; i<v[a].size(); ++i)
        {
            if(d[v[a][i].first]>d[a]+v[a][i].second)
            {
                d[v[a][i].first]=d[a]+v[a][i].second;
                if(inq[v[a][i].first]==0)
                {
                    inq[v[a][i].first]=1;
                    q.push(v[a][i].first);
                }
            }
        }
        q.pop();
        inq[a]=0;
    }
    bool ok=1;
    for(int i=1; i<=n && ok==1; ++i)
    {
        if(d[i]==oo)
        {
            d[i]=0;
        }
        if(d[i]!=r[i])
            ok=0;
    }
    if(ok==0)
        out<<"NU"<<'\n';
    else
        out<<"DA"<<'\n';
}

void read()
{
    in>>t;
    while(t>0)
    {
        int x, y, z;
        in>>n>>m>>s;
        for(int i=1; i<=n; ++i)
        {
            in>>r[i];
            d[i]=oo;
            inq[i]=0;
        }
        for(int i=1; i<=m; ++i)
        {
            in>>x>>y>>z;
            v[x].push_back(make_pair(y, z));
            v[y].push_back(make_pair(x, z));
        }
        solve();
        for(int i=1; i<=n; ++i)
        {
            v[i].clear();
        }
        for(int i=0; i<v[1].size(); ++i)
        {
            cout<<v[1][i].first;
        }
        --t;
    }
}

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