#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>

using namespace std;

// #define DEBUG 1
// #if DEBUG
// std::ifstream fin("_input.txt");
// #else
// #define fin std::cin
// #endif

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

int t;
const int inf = INT_MAX;

void read(vector<vector<pair<int, int>>> &graf, int m)
{
    for (int i = 0; i < m; i++)
    {
        int muchie1, muchie2, cost;
        fin >> muchie1 >> muchie2 >> cost;
        muchie1--;
        muchie2--;
        graf[muchie1].emplace_back(make_pair(muchie2, cost));
        graf[muchie2].emplace_back(make_pair(muchie1, cost));
    }
}

bool dijkstra(int nod_start, vector<vector<pair<int, int>>> graf, vector<int> verif, int nr_noduri)
{
    vector<bool> viz(nr_noduri, false);
    vector<int> dist(nr_noduri, inf);
    priority_queue<pair<int, int>> pq;

    dist[nod_start] = 0;
    viz[nod_start] = true;
    pq.push({0, nod_start});

    while (!pq.empty())
    {
        int el = pq.top().second;
        pq.pop();
        viz[el] = false;

        for (auto i : graf[el])
        {
            int cost = i.second;
            int vecin = i.first;

            if (dist[el] + cost < dist[vecin])
            {
                dist[vecin] = dist[el] + cost;
                if (viz[vecin] == false)
                {
                    viz[vecin] = true;
                    pq.push({-dist[vecin], vecin});
                }
            }
        }
    }

    return verif == dist;
}
int main()
{
    fin >> t;
    while (t--)
    {
        int n, m, nod_start;
        fin >> n >> m >> nod_start;
        vector<vector<pair<int, int>>> graf(n);
        vector<int> dist(n);
        nod_start--;

        for (auto &cost : dist)
            fin >> cost;

         read(graf, m);

          dijkstra(nod_start, graf, dist, n) ? cout << "DA" : cout << "NU";
          cout << "\n";
    }
}