#include <bits/stdc++.h>

#define nr 50002

using namespace std;

vector<pair<int,int>> muchii[nr];
int heap[nr];
int costuri[nr];
int poz_in_heap[nr];
int heap_lenght = 0;

void Update_Cost2(const int n)
{
int n_size = muchii[n].size();
    for (int i=0;i<n_size;i++)
    {
        int vecin = muchii[n][i].first;
        int cost = muchii[n][i].second;
        if (costuri[vecin] > cost + costuri[n])
        {
            costuri[vecin] = cost + costuri[n];
        }
    }
}

void Shift_Down(int n)
{
    while ((n*2 <= heap_lenght && costuri[heap[n]] > costuri[heap[n*2]])||(n*2+1 <= heap_lenght && costuri[heap[n]] > costuri[heap[n*2+1]]))
    {
        if (costuri[heap[n*2]] < costuri[heap[n*2+1]] || n*2+1 > heap_lenght)
        {
            swap(heap[n],heap[n*2]);
            swap(poz_in_heap[heap[n]],poz_in_heap[heap[n*2]]);
            n*=2;
        }
        else
        {
            swap(heap[n],heap[n*2+1]);
            swap(poz_in_heap[heap[n]],poz_in_heap[heap[n*2+1]]);
            n = n*2+1;
        }
    }
}

void Shift_Up(int n)
{
    while (n/2 && costuri[heap[n]] < costuri[heap[n/2]])
    {
        swap(heap[n],heap[n/2]);
        swap(poz_in_heap[heap[n]],poz_in_heap[heap[n/2]]);
        n/=2;
    }
}

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

    int nr_grafuri,n,m,sursa,rasp[nr],a,b,c;

    fin>>nr_grafuri;
    for (int k=0;k<nr_grafuri;k++)
    {

        fin>>n>>m>>sursa;
        for (int i=1;i<=n;i++)
        {
            fin>>rasp[i];
            costuri[i] = 1001;
        }

        for (auto& nod : muchii)
        {
            nod.clear();
        }

        for (int i=0;i<m;i++)
        {
            fin>>a>>b>>c;
            muchii[a].push_back(make_pair(b,c));
            muchii[b].push_back(make_pair(a,c));
        }

        costuri[sursa] = 0;
        poz_in_heap[sursa] = -1;
        Update_Cost2(sursa);

        for (int i=1;i<=n;i++)
        {
            if (i != sursa)
            {
                heap_lenght++;
                heap[heap_lenght] = i;
                poz_in_heap[i] = heap_lenght;
                Shift_Up(heap_lenght);
            }
        }

        while (heap_lenght > 0)
        {
            int rad_crt = heap[1];
            swap(heap[1],heap[heap_lenght]);
            swap(poz_in_heap[heap[1]],poz_in_heap[heap[heap_lenght]]);
            heap_lenght--;
            Shift_Down(1);
            poz_in_heap[rad_crt] = -1;

            Update_Cost2(rad_crt);
            int rad_crt_vec = muchii[rad_crt].size();
            for (int j=0;j<rad_crt_vec;j++)
            {
                int vec_crt = muchii[rad_crt][j].first;
                if (poz_in_heap[vec_crt] != -1)
                    Shift_Up(poz_in_heap[vec_crt]);
            }
        }

        int ok = 1;
        for (int i=1;i<=n;i++)
        {
            if (costuri[i] != rasp[i])
            {
                fout<<"NU\n";
                ok = 0;
                break;
            }
        }

        if (ok == 1)
        {
            fout<<"DA\n";
        }
    }

    fin.close();
    fout.close();

    return 0;
}