// ******************************************
//
// https://infoarena.ro/problema/distante
//
// $ g++ -std=c++11 -o distante.elf
//               -g -c distante.cpp
//
// $ ./distsnte.elf; echo $?


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


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
, VectorA       & adjacency_lists
, VectorU       & distances
)
;

bool
verify_distances
(
  size_t  const    start_vertex
, VectorA const  & adjacency_lists
, VectorU const  & 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  distances;
    VectorA  adjacency_lists;
    read_from_file (is,
                    start_vertex,
                    adjacency_lists,
                    distances);
    bool  ok;
    ok = verify_distances (start_vertex,
                           adjacency_lists,
                           distances);
    os << (ok ? "DA\n" : "NU\n");
  }

  return 0;
}


void
read_from_file
(
  std::istream  & is
, size_t        & start_vertex
, VectorA       & adjacency_lists
, VectorU       & distances
)
{
  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;
    auto  e = std::make_pair(b, c);
    auto  f = std::make_pair(a, c);
    A[a].push_back(e);
    A[b].push_back(f);
  }

  start_vertex = S;
  adjacency_lists.swap(A);
  distances.swap(D);
}


bool
verify_distances
(
  size_t  const    start_vertex
, VectorA const  & adjacency_lists
, VectorU const  & distances
)
{
  if (distances.at(start_vertex) != 0)
  {
    return false;
  }

  size_t  n = adjacency_lists.size();
  std::vector<int>  mark(n, 0);

  for (size_t  u = 0; n > u; ++u)
  {
    size_t  d_u = distances.at(u);
    auto const  & L =
      adjacency_lists.at(u);

    for (size_t  i = 0; L.size() > i; ++i)
    {
      auto const  & e = L.at(i);
      size_t  v = e.first;
      size_t  w_uv = e.second;
      size_t  d_v = distances.at(v);

      if (d_u + w_uv < d_v)
      {
         return false;
      }

      if (d_u + w_uv == d_v)
      {
        mark.at(v) = 1;
      }
    }
  }

  mark.at(start_vertex) = 1;

  return std::all_of(mark.begin(),
                     mark.end(),
                     [](int m) {
                       return 0 != m;
                     });
}