#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
#define NMAX 50005
#define x first
#define y second
#define INF 0x3f3f3f3f
ifstream f("distante.in");
ofstream g("distante.out");
vector < pair <int,int> > v[NMAX];
int t,m,n,s,D[NMAX];
int dh,H[NMAX];
void addheap(int x)
{
    int t,s,aux;
    H[++dh]=x;
    s=dh, t=s>>1;
    while (D[H[t]]>D[H[s]] && t>0)
    {
        aux=H[t], H[t]=H[s], H[s]=aux;
        s=t, t=s>>1;
    }
}
int extheap()
{
    int t,s,aux,r=H[1];
    H[1]=H[dh], H[dh--]=0;
    t=1, s=2;
    while (s<=dh)
    {
        if (s<dh && D[H[s]]>D[H[s+1]]) ++s;
        if (D[H[t]]<=D[H[s]]) break;
        aux=H[t], H[t]=H[s], H[s]=aux;
        t=s, s=t<<1;
    }
    return r;
}
void rez()
{
    int x,y,c,i;
    bool ok=true;
    memset(D,0x3f,sizeof(D));
    f>>n>>m>>s;
    for (i=1;i<=n;++i) f>>D[i];
    if (D[s]) ok=false;
    for (i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    for (i=1;i<=n;++i)
        addheap(i);
    while (dh>0)
    {
        x=extheap();
        for (auto it: v[x])
        {
            y=it.x, c=it.y;
            if (D[y]>D[x]+c)
                ok=false;
        }
    }
    if (ok) g<<"DA\n";
    else g<<"NU\n";
}
int main()
{
    int i;
    f>>t;
    for (i=0;i<t;++i)
        rez();
    return 0;
}