#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
#define Nmax 10000000
ifstream f("distante.in");
ofstream g("distante.out");
struct nod_cost
{
    int nod,cost;
};
nod_cost h[50001];
int t,ih,o,y,cst,i,j,n1,l,p,k,x,n,m,heap_node[50001],b[50001],dist[50001];
void up(int p)
{
    while(p>1 && h[p].cost<h[p/2].cost)
    {
        swap(heap_node[h[p].nod],heap_node[h[p/2].nod]);
        swap(h[p],h[p/2]);
        p/=2;
    }
}
void down(int p)
{
    if((p<<1)<=n && (p<<1)+1<=n && h[p<<1].cost<h[(p<<1)+1].cost && h[p<<1].cost<h[p].cost)
    {
        swap(heap_node[h[p].nod],heap_node[h[p<<1].nod]);
        swap(h[p],h[p<<1]);
        down(p<<1);
    }
    else
    if((p<<1)<=n && (p<<1)+1<=n && h[p<<1].cost>h[(p<<1)+1].cost && h[(p<<1)+1].cost<h[p].cost)
    {
        swap(heap_node[h[p].nod],heap_node[h[(p<<1)+1].nod]);
        swap(h[p],h[(p<<1)+1]);
        down((p<<1)+1);
    }
    else
    if((p<<1)<=n && h[p<<1].cost<h[p].cost)
    {
        swap(heap_node[h[p].nod],heap_node[h[p<<1].nod]);
        swap(h[p],h[p<<1]);
        down(p<<1);
    }
}

inline void cut(int k)
{
    swap(heap_node[h[k].nod],heap_node[h[n].nod]);
    swap(h[k],h[n]);
    n--;
    up(k);
    down(k);
}
inline void BuildHeap()
{
    for(int i=2;i<=n;i++)
        up(i);
}
inline int extractMin()
{
    return h[1].nod;
}
inline void Dijkstra(int p) //nodul p din graf
{
    int i,k,n1,ih,j;
    for(i=1;i<=n;i++)
    {
        heap_node[i]=i;
        h[i].nod=i;
        h[i].cost=Nmax;
    }
    h[p].cost=0;
    BuildHeap();
    while(n>1)
    {
        i=extractMin();
        ih=heap_node[i];
        for(k=0;k<v[i].size();k++)
            if(heap_node[v[i][k].first]<=n)
            {
                j=heap_node[v[i][k].first];
                o=v[i][k].first;
                if(h[j].cost>h[ih].cost+v[i][k].second)
                {
                    h[j].cost=h[ih].cost+v[i][k].second;
                    dist[o]=h[j].cost;
                    up(j);
                }
            }
        cut(ih);
    }
}
int main()
{
    f>>t;
    for(;t;t--)
    {
        vector<pair<int,int> >v[50001];
        f>>n>>m>>p;
        int n1=n;
        for(i=1;i<=n;i++)
            f>>b[i];
        for(i=1;i<=m;i++)
        {
            f>>x>>y>>cst;
            v[x].push_back(make_pair(y,cst));
        }
        Dijkstra(p);
        n=n1;
        for(i=1;i<=n && (dist[i]==b[i]) ;i++){}
        if(i-1==n) g<<"DA"<<'\n';
        else g<<"NU"<<'\n';
        //for(i=1;i<=n;i++) v[i].clear();
    }
}