#include<fstream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
ifstream in("distante.in");
ofstream out("distante.out");

#define Nmax 50001
#define INF ((1<<31)-1)

struct muchie
{
    int y, cost;
};

vector <muchie> a[Nmax];

int d[Nmax];
int n, m;
int h[Nmax], poz[Nmax];
int nh, start;
int sol[Nmax];

void schimba(int i1, int i2)
{
    swap(h[i1], h[i2]);

    poz[h[i1]]=i1;
    poz[h[i2]]=i2;
}

void urca(int i)
{
    while(i > 1 && d[h[i]] > d[h[i / 2]])
    {
        schimba(i , i / 2);
        i/=2;
    }
}

void coboara(int i)
{
    int bun = i, fs = i*2, fd = i*2+1;

    if(fs <= nh && d[h[fs]] < d[h[bun]])
        bun = fs;
    if(fd <= nh && d[h[fd]] < d[h[bun]])
        bun = fd;

    if(bun!=i)
    {
        schimba(bun, i);
        coboara(bun);
    }
}

void adauga(int x)
{
    h[++nh]=x;
    poz[x]=nh;
    urca(nh);
}

int sterge(int i)
{
    schimba(i, nh);
    nh--;
    coboara(i);
    urca(i);
}

void dijkstra(int x)
{
    nh=0;
    for(int i=1; i<=n; i++)
        d[i]=INF;
    d[x]=0;
    adauga(x);

    while(nh != 0)
    {
        x=h[1];
        sterge(1);

        for(size_t i=0 ;i < a[x].size(); i++)
        {
            int y=a[x][i].y;
            int cost=a[x][i].cost;
            if( d[x] + cost < d[y])
            {
                d[y] = d[x] + cost;
                if(poz[y] == 0)
                    adauga(y);
                else
                    urca(poz[y]);
            }
        }
    }
}

void afisare()
{
    int ok=1;
    for(int i=1; i<=n; i++)
    {
        if(d[i]==INF)
            d[i]=0;
        if(d[i] != sol[i])
        {
            ok=0;
            break;
        }
    }
    if(ok==0)
        out<<"NU\n";
    else
        out<<"DA\n";
}

void citire()
{
    int x, y, cost;
    in >> n >> m >> start;

    for(int i=1; i<=n ;i++)
        in>>sol[i];

    for(int i=1; i<=m; i++)
    {
        in>> x >> y >> cost;
        a[x].push_back({y, cost});
        a[y].push_back({x, cost});
    }
}

void reinit()
{
    memset(poz, 0, sizeof(poz));
    memset(d, 0, sizeof(d));
}

int main ()
{
    int t;
    in>>t;
    for(int i=1; i<=t; i++)
    {
        citire();
        dijkstra(start);
        afisare();
        reinit();
    }
    return 0;
}