#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream fin("distante.in");
ofstream fout("distante.out");

const int INF = 0x3f3f3f3f;
const int MAXN = 50000 + 16;

vector < pair < int, int > > Successor[MAXN];
int Heap[MAXN], Pos[MAXN], K;
int Distance[MAXN];
int N, M;

void Dijkstra(int);
void Heap_Sift(int);
void Heap_Percolate(int);

int main()
{
    int T;
    fin >> T;
    while(T--)
    {
        int Src;
        fin >> N >> M >> Src;

        int Test[MAXN];
        for(int i = 1; i <= N; ++i)
            fin >> Test[i];

        for(int i = 1; i <= M; ++i)
        {
            int x, y, c;
            fin >> x >> y >> c;
            Successor[x].push_back(make_pair(y, c));
            Successor[y].push_back(make_pair(x, c));
        }

        memset(Distance+1, INF, N * sizeof(int));
        memset(Pos+1, -1, N * sizeof(int));
        Dijkstra(Src);

        bool ok = true;
        for(int i = 1; i <= N && ok; ++i)
            if(Test[i] != Distance[i])
                ok = false;

        fout << (ok ? "DA" : "NU") << '\n';
    }

    return 0;
}

void Heap_Sift(int nod)
{
    while(nod <= K)
    {
        int child = nod << 1;

        if(child <= K)
        {
            if(child + 1 <= K && Distance[Heap[child+1]] < Distance[Heap[child]])
                child++;
        }
        else return;

        if(Distance[Heap[child]] < Distance[Heap[nod]])
        {
            swap(Heap[nod], Heap[child]);
            Pos[Heap[nod]] = nod;
            Pos[Heap[child]] = child;
        }
        else return;

        nod = child;
    }
}

void Heap_Percolate(int nod)
{
    while(nod > 1)
    {
        int father = nod >> 1;

        if(Distance[Heap[father]] < Distance[Heap[nod]])
        {
            swap(Heap[nod], Heap[father]);
            Pos[Heap[nod]] = nod;
            Pos[Heap[father]] = father;
        }
        else
            nod = 1;
    }
}

void Dijkstra(int start)
{
    Distance[start] = 0;

    Pos[Heap[K = 1] = start] = 1;
    while(K)
    {
        int BestTake = Heap[1];
        swap(Heap[1], Heap[K]);
        Pos[Heap[1]] = 1;
        K--;
        Heap_Sift(1);

        for(vector < pair < int, int > > :: iterator it = Successor[BestTake].begin();
            it != Successor[BestTake].end(); ++it)
        {
            int varf = (*it).first;
            int cost = (*it).second;
            if(Distance[varf] > Distance[BestTake] + cost)
            {
                Distance[varf] = Distance[BestTake] + cost;
                if(Pos[varf] == -1)
                {
                    Heap[++K] = varf;
                    Pos[Heap[K]] = K;
                    Heap_Percolate(K);
                }
                else
                    Heap_Percolate(Pos[varf]);
            }
        }
    }
}