#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#define Nmax 50050
#define inf 1<<30

using namespace std;

vector <int> G[Nmax],C[Nmax];
set < pair <int, int> > T;
int dist[Nmax],d[Nmax],N,M;

void Dijkstra(int x)
{
    int i,nod,cost;

    for(i=1;i<=N;i++)
        d[i] = inf;
    d[x] = 0;
    T.insert( make_pair(x, 0) );

    while(!T.empty())
    {
        nod = (*T.begin()).first;
        cost = (*T.begin()).second;
        T.erase(*T.begin());

        for(i=0;i<G[nod].size();i++)
            if(C[nod][i] + cost < d[G[nod][i]])
            {
                d[G[nod][i]] = C[nod][i] + cost;
                T.insert( make_pair(G[nod][i], d[G[nod][i]]));
            }
    }
}

bool verif()
{
    int i;
    for(i=1;i<=N;i++)
        if(d[i] != dist[i]) return false;
    return true;
}

int main()
{
    int i,a,b,c,Te,start,j;
    freopen("distante.in","r",stdin);
    freopen("distante.out","w",stdout);

    scanf("%d",&Te);

    for(i=0;i<Te;i++)
    {
        scanf("%d%d%d",&N,&M,&start);
        for(j = 0;j<N;j++)
        {
            G[j + 1].clear();
            C[j + 1].clear();
            scanf("%d",&dist[j + 1]);
        }

        for(j = 0;j<M;j++)
        {
            scanf("%d%d%d",&a,&b,&c);

            G[a].push_back(b);
            C[a].push_back(c);
        }

        Dijkstra(start);
        if(verif()) printf("DA\n");
        else printf("NU\n");
    }
}