#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

vector < pair<int,int> > graf[50001] ;
int d[50001] ;
class comparvf
{
    public:
    bool operator () ( int &a , int &b )
    {
        return d[a] > d[b] ;
    }

};
priority_queue <int,vector<int> , comparvf> H ;
int n , m , nod , dz[50001] ;

ifstream fin ("distante.in") ;
ofstream fout("distante.out") ;

void citire ()
{
    int x , y , c , j ;
    fin >> n >> m >> nod ;
    memset(d,0,50001*sizeof(int)) ;
    memset(dz,0,50001*sizeof(int)) ;
    for ( j = 1 ; j <= n ; j++ )
        fin >> dz[j] ;
    for ( j = 1 ; j <= m ; j++ )
    {
        fin >> x >> y >> c;
        graf[x].push_back(make_pair(y,c)) ;
        graf[y].push_back(make_pair(x,c)) ;
    }
}

void dijkstra()
{
    int p , j ;
    H.push(nod) ;
    for ( j = 1 ; j <= n ; j++ )
        d[j] = 1000001 ;
    d[nod] = 0 ;
    while ( !H.empty() )
    {
        p = H.top() ;
        H.pop() ;
        for ( j = 0 ; j < graf[p].size() ; j++ )
        {
            if ( d[graf[p][j].first] > graf[p][j].second + d[p] )
            {
                d[graf[p][j].first] = graf[p][j].second + d[p] ;
                H.push(graf[p][j].first) ;
            }
        }
    }
}

int main()
{
    int i , j , NR ;
    bool corect ;
    fin >> NR ;
    for ( i = 1 ; i <= NR ; i++ )
    {
        citire() ;
        dijkstra() ;
        corect = true ;
        for ( j = 1 ; j <= n ; j++ )
            if ( d[j] != dz[j] )
                corect = false ;
        if ( corect == true )
            fout << "DA" ;
        else
            fout << "NU" ;
        for ( j = 1 ; j <= n ; j++ )
            graf[j].clear() ;
        fout << endl ;
    }
}