#include <fstream>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#define inf 9999999

using namespace std;

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

void distante()
{
    vector<int> value;
    int T, n, m, sursa;
    bool verif;
    fin >> T;
    for (int index = 1; index <= T; index++)
    {
        verif = true;
        fin >> n >> m >> sursa;

        value.resize(n + 1);
        int Bronzarel[n + 1];
        for (int j = 1; j <= n; j++)
            fin >> Bronzarel[j];

        int x, y; 
        int i;
        // fin >> n >> m >> sursa;
        // int value[n + 1]; // in value se retin distantele de la nodul src la restul
        vector<int> value;
        value.resize(n + 1);
        vector<vector<pair<int, int> > > adj;
        adj.resize(n + 1);
        set<pair<int, int> > set_cost_nod; // set_cost_nod retine nodurile inca neprocesate si costul pt a ajunge in ele
        // folosim set pt ca atunci cand vom lua un alt nod vrem sa il luam pe cel cu costul minim
        //  ce se afla la un mom de timp in set_nod_cost, inseamna ca acele noduri nu au fost inca procesate.
        for (int i = 0; i < m; ++i)
        {
            int cost;
            fin >> x >> y >> cost;
            adj[x].push_back(make_pair(y, cost));
        }
        for (i = 1; i <= n; ++i)
        {
            value[i] = inf;
        }
        value[sursa] = 0;
        set_cost_nod.insert(make_pair(0, sursa)); // cost 0 pt nodul sursa 1
        while (!set_cost_nod.empty())
        {
            int nod = (*set_cost_nod.begin()).second; // luam nodul curent
            set_cost_nod.erase(set_cost_nod.begin()); // pop nod crr si cost
            for (int i = 0; i < adj[nod].size(); ++i)
            {
                int nod_dest = adj[nod][i].first;             // nod_dest = este nodul destinatie de la care plecam din nodul crr("nod")
                int cost_dest = adj[nod][i].second;           // costul muchiei de la nod la nod_dest
                if (value[nod] + cost_dest < value[nod_dest]) // value[nod] retine dist de la nodul src(1) la nodul crr (nod)
                // adugam costul de la nod crr la nod dest sa vedem daca gasim o cale mai "ieftina" din nodul src(1) la nod dest
                {
                    if (value[nod_dest] != inf)
                    {
                        set_cost_nod.erase(set_cost_nod.find(make_pair(value[nod_dest], nod_dest)));
                        // in cazul in care value[nod_dest] !=inf adica dist din 1 la nod_dest a mai fost actualizata si totusi s-a gasit
                        // un drum mai scurt, vom scoate valoarea veche din set_nod_cost pt a o reactualiza mai jos in value si pt a face push
                        // in set la noua valoare pt nod_dest
                    }
                    // deci se respecta cond din if
                    value[nod_dest] = value[nod] + cost_dest;                  // actualizam noul cost pt nodul dest
                    set_cost_nod.insert(make_pair(value[nod_dest], nod_dest)); // inseram in set (costul de a ajung din src la nod_dest, nod dest)
                    // la urmatoarele iteratii se va lua nod_dest ca fiind noul nod crr
                }
            }
        }
        // for (int i = 2; i <= n; ++i)
        //     if (value[i] != inf)
        //         fout << value[i] << " ";
        //     else
        //         fout << 0 << " ";
        for (i = 1; i <= n; i++)
        {
            if (value[i] != Bronzarel[i])
                verif = false;
        }
        if (!verif)
        {
            fout << "NU" << endl;
            value.clear();
            adj.clear();
            set_cost_nod.clear();
        }
        else
        {
            fout << "DA" << endl;
            value.clear();
            adj.clear();
            set_cost_nod.clear();
        }
    }
}


int main()
{
    distante();
    return 0;
}