//
//  main.cpp
//  Distante
//
//  Created by Mara Dascalu on 05/01/2022.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bits/stdc++.h>

#define INF INT_MAX

using namespace std;

typedef std:: pair<int, int> Pair;

ifstream input("distante.in");
ofstream output("distante.out");

vector<int> dijkstra(int start);
bool verify (vector<int> &dist, vector<int> &correct_dist);

int nodes, edges;
vector<vector<Pair>> adj_weight;
vector<int> dist;
vector<int> correct_dist;

int main(int argc, const char * argv[])
{
    int task, start;
    input >> task;
    
    for (int i = 0 ; i < task ; i++)
    {
        input >> nodes >> edges >> start;
        
        dist.resize(nodes + 1);
        for (int j = 1 ; j <= nodes ; j++)
            input >> dist[j];
        
        adj_weight.resize(nodes + 1);
        for (int j = 0 ; j < edges ; j++)
        {
            int x, y, cost;
            input >> x >> y >> cost;
            adj_weight[x].push_back(make_pair(y, cost));
            adj_weight[y].push_back(make_pair(x, cost));
        }
        
        correct_dist.resize(nodes + 1);
        correct_dist = dijkstra(start);
        
        if (verify(dist, correct_dist))
            output << "DA\n";
        else output << "NU\n";
        
        dist.clear();
        correct_dist.clear();
        adj_weight.clear();
    }
}

vector<int> dijkstra(int start)
{
    vector<bool> visited;
    vector<int> dist;      //the vector that stores the minimum distance from the start node to the other nodes
    priority_queue<Pair, vector<Pair>, greater<Pair>> queue_adj;  //queue in which we store the adjacent nodes and the costs of the adjacent edges of the currently visited node in order to have the order of traversal
                                                                  //we will first retain the cost and then the adjacent node so that we can easily obtain at each iteration the node that has the associated edge of minimum cost
    dist.assign(nodes + 1, INF);
    visited.assign(nodes + 1, false);

    queue_adj.push(make_pair(0, start));   //for the start node we have the cost 0 to get to it
    dist[start] = 0;

    while (!queue_adj.empty())
    {
        int node = get<1>(queue_adj.top());
        queue_adj.pop();

        if (visited[node])
        {
            continue;
        }
        else
        {
            visited[node] = 1;
        }
        
        for (int i = 0; i < adj_weight[node].size(); i++)        //for all adjacent nodes of node
        {
            int child = get<0>(adj_weight[node][i]);
            int weight = get<1>(adj_weight[node][i]);

            if (dist[node] + weight < dist[child])      //we check if for the adjacent nodes we find a shorter path through node than the already traversed ones
            {
                dist[child] = dist[node] + weight;
                queue_adj.push(make_pair(dist[child], child));
            }
        }
    }

    replace(dist.begin(), dist.end(), INF, 0);
    
    return dist;
}

bool verify (vector<int> &dist, vector<int> &correct_dist)
{
    for (int i = 1 ; i < dist.size() ; i++)
        if (dist[i] != correct_dist[i])
            return false;
    
    return true;;
}