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

using namespace std;

ifstream f("distante.in");
ofstream o("distante.out");


class Graph
{
    vector<vector<pair<int, int>>> adjListW;
    static const int INF;

public:
    int size;
    Graph(int n)
    {
        size = n + 1;
        adjListW.resize(size);
    }
    void addEdgeDW(int start, int end, int weight)
    {
        adjListW[start].push_back(make_pair(end, weight));
    }
    vector<int> Dijkstra(int src)
    {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> dist(size, INF);
        dist[src] = 0;
        pq.push(make_pair(0, src));
        while (!pq.empty())
        {
            int u = pq.top().second;
            pq.pop();
            for (auto i : adjListW[u])
            {
                int v = i.first;
                int weight = i.second;
                if (dist[v] > dist[u] + weight)
                {
                    dist[v] = dist[u] + weight;
                    pq.push(make_pair(dist[v], v));
                }
            }
        }
        return dist;
    }
};
const int Graph::INF=2147483647;


int main()
{
    int N, M, src;
    int x, y, w;
    int t;
    f >> t;
    for (int i = 1; i <= t; i++)
    {
        f >> N >> M >> src;
        Graph g(N);
        vector<int> bronzarel(N+1);
        for (int i = 1; i <= N; i++)
            f >> bronzarel[i];
        for (int i = 1; i <= M; i++)
        {
            f >> x >> y >> w;
            g.addEdgeDW(x, y, w);
        }
        vector<int> dist=g.Dijkstra(src);
        int ok=1;  	
        for(int i=1;i<=N;i++)
        {
            if(bronzarel[i]!=dist[i])
            {
                ok=0;
                o<<"NU"<<endl;
                break;
            }
        }
        if(ok==1)
            o<<"DA"<<endl;
    }

    return 0;
}