// ****************************************** 
// $ g++ -o distante -std=c++11 distante.cpp
// $ ./distsnte; echo $?


#include <utility>
#include <set>
#include <vector>
#include <fstream>


using  LongU = unsigned long;
using  size_t = std::size_t;
using  Endpoint = std::pair<size_t, LongU>;
template  < typename T >
using  VectorT = std::vector<T>;
using  VectorU = VectorT<LongU>;
using  VectorE = VectorT<Endpoint>;
using  VectorA = VectorT<VectorE>;


const LongU max_c = 1000;
const LongU max_n = 50000;
const LongU max_d = max_c + (max_n - 1);
const LongU infinity = max_d + 1;


int
main
(
  void
)
;

int
demo
(
  void
)
;

void
read_from_file
(
  std::istream  & is
, size_t  & start_vertex
, VectorU  & expected_distances
, VectorA  & adjacency_lists
)
;

void
dijkstra
(
  size_t  const start_vertex
, VectorA const   & adjacency_lists
, VectorU  & actual_distances
)
;


int
main
(
  void
)
{
  
  int status_code = 3;

  try
  {
    
    status_code = demo();

  }
  catch ( ... )
  {
    
    status_code = 2;

  }

  return status_code;

}


int
demo
(
  void
)
{
  
  std::ifstream  is("distante.in");
  std::ofstream  os("distante.out");

  int  T;

  is >> T;

  int  i;

  for (i = 0; T > i; ++i)
  {
    
    size_t  start_vertex;
    VectorU  expected_distances;
    VectorA  adjacency_lists;
    read_from_file (is,
                    start_vertex,
                    expected_distances,
                    adjacency_lists);
    VectorU  actual_distances;
    dijkstra (start_vertex,
              adjacency_lists,
              actual_distances);
    bool  ok = (actual_distances ==
                expected_distances);
    os << (ok ? "DA\n" : "NU\n");

  }

  return 0;

}


void
read_from_file
(
  std::istream  & is
, size_t  & start_vertex
, VectorU  & expected_distances
, VectorA  & adjacency_lists
)
{
  
  size_t  N;
  size_t  M;
  size_t  S;

  is >> N;
  is >> M;
  is >> S;

  S = S - 1;

  VectorU  D(N);
  VectorA  A(N);

  size_t  i;

  for (i = 0; N > i; ++i)
  {
    
    is >> D[i];

  }

  size_t  a;
  size_t  b;
  LongU  c;
  
  for (i = 0; M > i; ++i)
  {
    
    is >> a;
    is >> b;
    is >> c;
    a = a - 1;
    b = b - 1;
    Endpoint  e = std::make_pair(b, c);
    Endpoint  f = std::make_pair(a, c);
    A[a].push_back(e);
    A[b].push_back(f);

  }

  start_vertex = S;
  expected_distances.swap(D);
  adjacency_lists.swap(A);

}


void
dijkstra
(
  size_t  const start_vertex
, VectorA const   & adjacency_lists
, VectorU  & actual_distances
)
{

  typedef  std::pair<LongU, size_t>
           Estimate;
  typedef  std::set<Estimate>
           PriorityQueue;
  typedef  PriorityQueue::iterator
           PriorityQueueIterator;
  typedef  VectorT<PriorityQueueIterator>
           VectorJ;


  VectorA const  & A = adjacency_lists;
  size_t  N = A.size();
  size_t  S = start_vertex;
  PriorityQueue  Q;
  VectorJ  J(N);
  VectorU  U(N);
  VectorU  D(N);
  size_t  i;

  for (i = 0; N > i; ++i)
  {
    
    LongU  g = (S == i) ? 0 : infinity;     
    Estimate  e = std::make_pair(g, i);
    auto  p = Q.insert(e);
    J[i] = p.first;
    U[i] = 1;
    
  }

  for (i = 0; N > i; ++i)
  {
    
    auto  p = Q.begin();
    size_t  u = p->second;
    size_t  d = p->first;
    D[u] = d;
    Q.erase(p);
    U[u] = 0;
    
    if (i != N - 1)
    {
     
      size_t  j;

      for (j = 0; A[u].size() > j; ++j)
      {
        
        auto  q = A[u][j];
        size_t  v = q.first;
        LongU  w = q.second;
        LongU  g = d + w;
        
        if (U[v] && (g < J[v]->first))
        {

          Q.erase(J[v]);
          Estimate  e = std::make_pair(g, v);
          auto  r = Q.insert(e);
          J[v] = r.first;
          
        }
        
      }

    }

  }

  actual_distances.swap(D);

}