#include <fstream>

using namespace std;
ifstream cin("distante.in");
ofstream cout("distante.out");
int n,i,j,viz[50005],a[1005][1005],m,d[50005],x,y,cost,mx=999999999,poz,mn,k,p,v[50005],ok,t,l;
int main()
{
    cin>>t;
    for(l=1; l<=t; l++)
    {
        cin>>n>>m>>p;ok=0;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                if (i!=j) a[i][j]=mx;
            }
        }
        for(i=1;i<=n;i++) cin>>v[i];
        for(i=1;i<=m;i++)
        {
            cin>>x>>y>>cost;
            a[x][y]=cost;
        }
        d[p]=0;
        d[0]=mx;
        viz[p]=1;
        for(i=1; i<=n; i++)
        {
            viz[i]=0;
            d[i]=a[p][i];
        }
        for(k=1; k<n; k++)
        {
            poz=0;
            mn=mx;
            for(i=1; i<=n; i++)
            {
                if(d[i]!=0&&d[i]!=mx&&viz[i]==0&&d[i]<mn)
                {
                    mn=d[i];
                    poz=i;
                }
            }
            viz[poz]=1;
            for(i=1; i<=n; i++)
            {
                if(viz[i]==0&&d[poz]+a[poz][i]<d[i]) d[i]=d[poz]+a[poz][i];
            }
        }
        for(i=1; i<=n; i++)
        {
            if(d[i]==mx) d[i]=0;
            if(d[i]!=v[i]) ok=1;
        }
        if(ok==1) cout<<"NU"<<'\n';
        else cout<<"DA"<<'\n';
    }

    return 0;
}