#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
///distante
/**
t- nr grafu
n noduri
m muchii
s nod sursa
dn++ cost calc de future coleg de camera la nebuni
dm++ nod nod cost
d[] dement calc
*/
#define pb push_back
#define cin in
#define cout out
int cost[50001],d[50001],n,m,s,t;

struct compara
{
    bool operator()(int x, int y)
    {
        return cost[x] > cost[y];
    }
};
priority_queue<int, vector<int>, compara> q;
queue <bool>iq;
bool masca[50001];
vector <pair<int,int>>v[50001];

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

int krusadi(int x)
{
    q.push(x);
    int nod;
    while (!q.empty())
    {
        nod=q.top();
        q.pop();
        masca[nod]=false;
        for (auto coleg:v[nod])
        {
            int colegu=coleg.first;
            int chirie=coleg.second;
            if (cost[colegu]==0 || cost[colegu]>cost[nod]+chirie)
            {
                cost[colegu]=cost[nod]+chirie;
                if (masca[colegu]==false)
                {
                q.push(colegu);
                masca[colegu]=true;
                }

            }
        }
    }
}
/*
void afis()
{
    for (int i=0;i<n;i++)
    {
        cout<<i<<": ";
        for (auto j:v[i])
        cout<<j.first<<" "<<j.second<<", ";
        cout<<'\n';
    }
}**/

void cit()
{
    int a,b,ca;
    cin>>n>>m>>s;
    for (int i=1;i<=n;i++)
        cin>>d[i];
    for (int i=0;i<m;i++)
    {
        cin>>a>>b>>ca;
        v[a].pb(make_pair(b,ca));
    }
    krusadi(s);
    bool aw=true;
    for (int i=1;i<=n;i++)
        if (d[i]!=cost[i])
            aw=false;
    iq.push(aw);
}

int main()
{
    cin>>t;
    for (int e=0;e<t;t--)
    {
    cit();
    for (int i=0;i<n;i++)
        v[i].clear();
    }
    /*for (int i=1;i<=n;i++)
        cout<<i<<": "<<cost[i]<<" ";
    */
    while (!iq.empty())
    {
        if (iq.front()==true)
        cout<<"DA"<<'\n';
    else
        cout<<"NU"<<'\n';
        iq.pop();
    }
    return 0;
}