#include<iostream>
#include<fstream>
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
struct mat
{
    long a[100][100];
    long dis[1000];
    long n,m,s;
}v[1000];
int T,d[1000];
void cit()
{
    f>>T;
    for(int i=1;i<=T;i++)
    {
        f>>v[i].n>>v[i].m>>v[i].s;
        for(int j=1;j<=v[i].n;j++)
        {
            f>>v[i].dis[j];
        }
        int x,y,z;
        for(int j=1;j<=v[i].m;j++)
        {
            f>>x>>y>>z;
            v[i].a[x][y]=z;
        }
        for(int k=1;k<=v[i].n;k++)
        {
            for(int l=1;l<=v[i].n;l++)
            {
                if(k!=l)
                {
                    if(v[i].a[k][l]==0)
                        v[i].a[k][l]=100000;
                }
            }
        }
    }


}
void dij(int nod,int gf)
{
    int viz[1000],tata[1000],k,ok,mn;
    for(int i=1;i<=v[gf].n;i++)
    {
        tata[i]=k;
        viz[i]=0;
        d[i]=v[gf].a[nod][i];
    }
    tata[nod]=0;
    viz[nod]=1;ok=1;
    while(ok)
    {
        mn=10000;
        for(int i=1;i<=v[gf].n;i++)
        {
            if(viz[i]==0&&mn>d[i])
            {
                mn=d[i];
                k=i;
            }
        }
        if(mn!=10000)
        {
            viz[k]=1;
            for(int i=1;i<=v[gf].n;i++)
            {
                if(viz[i]==0&&d[i]>d[k]+v[gf].a[k][i])
                {
                    d[i]=d[k]+v[gf].a[k][i];
                    tata[i]=k;
                }
            }
        }
        else
            ok=0;
    }

}
int main()
{
    cit();
    for(int i=1;i<=T;i++)
    {
        dij(v[i].s,i);
        int b=1;
        for(int j=1;j<=v[i].n;j++)
        {
            if(d[j]!=v[i].dis[j])b=0;
        }
        if(b==1)g<<"DA\n";
        else
            g<<"NU\n";
    }

}