// ******************************************                                
//                                                                           
// https://infoarena.ro/problema/distante                                    
//                                                                           
// $ g++ -std=c++11 -o distante.elf                                          
//               -g -c distante.cpp                                          
//                                                                           
// $ ./distante.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;                                        
                     });                                                     
}