#include <fstream>
#include <vector>
#define INF 2000000001
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int d[50011],a[50011],coord[50011],nr;
void up(int k)
{
    if(k==1)
        return;
    if(d[a[k]]<d[a[k/2]])
    {
        swap(coord[a[k]],coord[a[k/2]]);
        swap(a[k],a[k/2]);
        up(k/2);
    }
}
void down(int k)
{
    int p=k*2;
    if(p>nr)
        return;
    if(p+1<=nr && d[a[p+1]]<d[a[p]])
        p++;
    if(d[a[k]]>d[a[p]])
    {
        swap(coord[k],coord[p]);
        swap(a[k],a[p]);
        down(p);
    }
}
bool inheap[50011];
int D[50011],s;
vector <pair<int,int>> v[50011];
void dijkstra()
{
    nr=1;
    a[1]=s;
    coord[1]=1;
    inheap[1]=1;
    while(nr)
    {
        int k=a[1];
        a[1]=a[nr];
        inheap[k]=0;
        nr--;
        down(1);
        if(d[k]!=D[k])
        {
            g<<"NU";
            return;
        }
        for(int i=0;i<v[k].size();i++)
        {
            if(d[v[k][i].first]>d[k]+v[k][i].second)
            {
                d[v[k][i].first]=d[k]+v[k][i].second;
                if(inheap[v[k][i].first]==0)
                {
                    inheap[v[k][i].first]=1;
                    nr++;
                    a[nr]=v[k][i].first;
                    coord[v[k][i].first]=nr;
                }
                up(coord[v[k][i].first]);
            }
        }
    }
    g<<"DA";
}
int T,t,i,n,m,x,y,z;
int main()
{
    f>>T;
    for(t=1;t<=T;t++,g<<'\n')
    {
        f>>n>>m>>s;
        for(i=1;i<=n;i++)
        {
            v[i].clear();
            d[i]=a[i]=INF;
            f>>D[i];
        }
        d[s]=0;
        for(i=1;i<=m;i++)
        {
            f>>x>>y>>z;
            v[x].push_back(make_pair(y,z));
            v[y].push_back(make_pair(x,z));
        }
        dijkstra();
    }
    return 0;
}