#include <iostream>
#include <fstream>
#include <string.h>
#define maxN 50005
#define maxM 100005
#define maxT 11
#define INF 0x3f3f
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");

int n,m,t,s,d[maxN],d_min[maxN],e[maxM][3];

void read()
{
    int i;
    f>>n; f>>m; f>>s;
    for(i=1; i<=n ;i++)
        f>>d_min[i];
    for(i=0; i<m ;i++)
    {
        f>>e[i][0];
        f>>e[i][1];
        f>>e[i][2];
    }
}

int valid_sol()
{
    for(int i=1; i<=n ;i++)
        if(d[i]!=d_min[i])
            return 0;
    return 1;
}

void bellman()
{
    int i,j,k,c,ok,nr;
    d[s]=0;
    for(ok=nr=1; ok && nr<n ;nr++)
    {
        for(ok=k=0; k<m ;k++)
        {
            i=e[k][0];
            j=e[k][1];
            c=e[k][2];
            if(d[j]>d[i]+c)
            {
                d[j]=d[i]+c;
                ok=1;
            }
        }
    }
    if(valid_sol())
        g<<"DA"<<"\n";
    else
        g<<"NU"<<"\n";
}

void distante()
{
    int i;
    f>>t;
    if(t)
    {
        memset(d_min,0,sizeof(d_min));
        memset(d,0x3f3f,sizeof(d));
        for(i=1; i<=t ;i++)
        {
            read();
            bellman();
        }
    }
}

int main()
{
    distante();
    return 0;
}