#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int distante[50010],d[50010], n,m,start;
struct my_struct {

    int nod, cost;
}t, nod_current;
vector<my_struct> v[250022];
queue<int>_q;
int viz[10001];
void marcare(int n)
{
    int k = 10000101;
    for (int i = 1; i <= n; i++)
    {
        d[i] = k;
    }
}
void read(int &N,int &M, int &start)
{

    f>>N>>M>>start;
    for(int i=1;i<=N;i++)
       {
            f>>distante[i];
            viz[i]=0;
            v[i].clear();
       }
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        f>>a>>t.nod>>t.cost;
        v[a].push_back(t);
    }

}

void  bellman_ford(int a)
{

    _q.push(a);
    viz[a] = 1;
    d[a] = 0;
    int nod_din_coada = 0;
    while (!_q.empty())
    {
        nod_din_coada = _q.front();
        viz[nod_din_coada] = 0;
        //de fiecare data cand trecem prin aceset nod-->nod_din_coada crestem un contor pt el si daca am trecut de m
        // cand e cost negativ, revine prin nod_din_coada
        _q.pop();
        for (int i = 0; i < v[nod_din_coada].size(); i++)
        {
            nod_current = v[nod_din_coada][i];
            if (d[nod_din_coada] + nod_current.cost < d[nod_current.nod])
            {
                d[nod_current.nod] = d[nod_din_coada] + nod_current.cost;
                if (!viz[nod_current.nod])
                {
                    _q.push(nod_current.nod);
                    viz[nod_current.nod] = 1;
                }
            }
        }
    }
}
int is_in(int nods_number)
{

    for(int i=1;i<=nods_number;i++)
    {
        if(d[i]!=distante[i])return 0;
    }
    return 1;
}
void solve(int n)
{

    if(is_in(n))
    {
        g<<"DA"<<'\n';
    }
    else
        g<<"NU"<<'\n';


}
int main(){
    int nr_grafs=0;
    f>>nr_grafs;
    for(int i=1;i<=nr_grafs;i++)
    {

        read(n,m,start);
        marcare(n);

        bellman_ford(start);
        solve(start);
    }

}