#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define N 50003
using namespace std;

int distanteCalculate[N];
vector <vector<pair <int, int>>> muchiiCuCost(N + 1);

vector <int> dijkstra(int start)
{
    vector <int> distante(N + 1, INT_MAX); ///initial distantele sunt egale cu infinit
    vector <int> inCoada(N + 1, 0);
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater<pair <int, int>>> coada; ///perechi {cost, nod}
    distante[start] = 0;
    coada.push({0, start});
    inCoada[start] = 1;
    while (!coada.empty())
    {
        int nodCurent = coada.top().second;
        coada.pop();
        inCoada[nodCurent] = 0;
        for (int i = 0; i < muchiiCuCost[nodCurent].size(); i++)
        {
            int vecin, cost_vecin;
            vecin = muchiiCuCost[nodCurent][i].first;
            cost_vecin = muchiiCuCost[nodCurent][i].second;
            if (distante[nodCurent] + cost_vecin < distante[vecin])
    ///daca distanta pana la nodul curent + costul pana la nodul adiacent < distanta nodului adiacent, actualizam aceasta distanta
            {
                distante[vecin] = distante[nodCurent] + cost_vecin;
                if (inCoada[vecin] == 0)
                {
                    coada.push({distante[vecin], vecin});
                    inCoada[vecin] = 1;
                }
            }
        }
    }
    return distante;
}

int main()
{
    ifstream fin("distante.in");
    ofstream fout("distante.out");
    int n, m, st, dr, cost, nrGrafuri, start;
    fin >> nrGrafuri;
    for (int contor = 1; contor <= nrGrafuri; contor++)
    {
        fin >> n >> m >> start;
        for (int i = 1; i <= n; i++)
            fin >> distanteCalculate[i];
        for (int i = 1; i <= m; i++)
        {
            fin >> st >> dr >> cost;
            muchiiCuCost[st].push_back(make_pair(dr, cost));
            muchiiCuCost[dr].push_back(make_pair(st, cost));
        }
        vector <int> rez = dijkstra(start);
        int ok = 1;
        for (int i = 1; i <= n; i++)
           if (rez[i] != distanteCalculate[i])
           {
               ok = 0;
               break;
           }
        if (ok == 0)
            fout << "NU" << "\n";
        else
            fout << "DA" << "\n";
        for (int i = 1; i <= n; i++)
            muchiiCuCost[i].clear();
    }
    fin.close();
    fout.close();
    return 0;
}