#include <cstdio>
using namespace std;

FILE *in = fopen("distante.in","r");
FILE *out = fopen("disteante.out","w");

struct graf
{
    int nod, dist;
    graf *urm;
};

int n, m, s;

graf *a[50001];

const int inf=1<<30;
int dist[50001], viz[50001], poz[50001], k, v[50001];

void adaugare(int i, int nod, int dist)
{
    graf *q = new graf;
    q->nod = nod;
    q->dist = dist;
    q->urm = a[i];
    a[i] = q;
}

void citire()
{
    fscanf(in, "%d %d %d", &n, &m, &s);
    for(int i=1; i<=n; i++)
        fscanf(in, "%d", &v[i]);
    int x,y,z;
    for(int i=1; i<=m; i++)
    {
        fscanf(in, "%d %d %d", &x, &y, &z);
        adaugare(x, y, z);
    }
}

void schimbare(int i, int j)
{
    int t = viz[i];
    viz[i] = viz[j];
    viz[j] = t;
}

void upheap(int nod)
{
    int tata;
    while ( nod != 1 )
    {
        tata = nod >> 1;

        if ( dist[ viz[tata] ] > dist[ viz[nod] ] )
        {
            poz[ viz[nod] ] = tata;
            poz[ viz[tata] ] = nod;

            schimbare(tata, nod);

            nod = tata;
        }
        else
            nod = 1;
    }
}

void downheap(int nod)
{
    int f;
    while ( nod <= k )
    {
        f = nod;
        if ( (nod<<1) <= k )
        {
            f = nod << 1;
            if ( f + 1 <= k )
                if ( dist[ viz[f + 1] ] < dist[ viz[f] ] )
                    f++;
        }
        else
            return;

        if ( dist[ viz[nod] ] > dist[ viz[f] ] )
        {
            poz[ viz[nod] ] = f;
            poz[ viz[f] ] = nod;

            schimbare(nod, f);

            nod = f;
        }
        else
            return;
    }
}

void dijkstra_heap()
{
    for ( int i = 1; i <= n; i++ )
    {
        if(i!=s)
        {
            dist[i] = inf;
            poz[i] = -1;
        }
    }
    poz[s] = 1;

    viz[++k] = s;

    while ( k )
    {
        int minn = viz[1];
        schimbare(1, k);
        poz[ viz[1] ] = s;
        --k;

        downheap(s);

        graf *q = a[minn];

        while ( q )
        {
            if ( dist[q->nod] > dist[minn] + q->dist )
            {
                dist[q->nod] = dist[minn] + q->dist;

                if ( poz[q->nod] != -1 )
                    upheap( poz[q->nod] );
                else
                {
                    viz[++k] = q->nod;
                    poz[ viz[k] ] = k;
                    upheap( k );
                }
            }
            q = q->urm;
        }
    }
}

int main()
{
    int x;
    fscanf(in, "%d", &x);
    for(int i=1; i<=x; i++)
    {
    citire();
    dijkstra_heap();
    int ok=1;
    for(int i=1; i<=n; i++)
        if(dist[i]==inf)
            if(v[i]!=0)
                ok=0;
        else
            if(dist[i]!=v[i])
                ok=0;
    if(ok==1)
        fprintf(out, "DA\n");
    else
        fprintf(out, "NU\n");
    }
    return 0;
}