#include<stdio.h>
#define MAX 100000
int ultim[2*MAX],prev[2*MAX],dist[MAX],coada[MAX];
int link[2*MAX],distof2[2*MAX],mindist[50000];
int main()
{
    FILE *fin,*fout;
    fin=fopen("distante.in","r");
    fout=fopen("distante.out","w");
    int t;
    fscanf(fin,"%d",&t);
    while(t)
    {
        int n,m,s;
        fscanf(fin,"%d%d%d",&n,&m,&s);
        int i;
        for(i=1; i<=n; i++)
            fscanf(fin,"%d",&mindist[i]);
        for(i=1; i<=m; i++)
        {
            int x,y,z;
            fscanf(fin,"%d%d%d",&x,&y,&z);
            prev[i]=ultim[x];
            distof2[i]=z;
            ultim[x]=i;
            link[i]=y;
            prev[i+MAX]=ultim[y];
            distof2[i+MAX]=z;
            ultim[y]=i+MAX;
            link[i+MAX]=x;
        }
        for(i=1; i<=n; i++)
            if(i!=s)
                dist[i]=MAX;
            else
                dist[i]=0;
        int first=0,last=1;
        coada[0]=s;
        while(first<=last)
        {
            int i,p=ultim[coada[first]];
            while(p!=0)
            {
                if(dist[coada[first]]+distof2[p]<dist[link[p]])
                {
                    dist[link[p]]=dist[coada[first]]+distof2[p];
                    coada[last]=link[p];
                    last++;
                }
                p=prev[p];
            }
            first++;
        }
        for(i=1; i<=n; i++)
            if(mindist[i]!=dist[i])
            {
                fprintf(fout,"NU\n");
                i=n+2;
            }
        if(i<n+2)
            fprintf(fout,"DA\n");
        for(i=1;i<=m;i++)
            prev[i]=prev[i+MAX]=link[i]=ultim[i]=link[i+MAX]=ultim[i+MAX]=0;
        t--;
    }
    return 0;
}