#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

#define nrmax 50001
#define inf 2000000000
#define pb push_back
#define mp make_pair
#define nod first
#define cost second
using namespace std;

ifstream f("distante.in");
ofstream g("distante.out");

vector < pair < int , int > > G[nrmax];
bool used[nrmax];
int d[nrmax];
int dist[nrmax];
int t, n, m, x, y , z , start ;
queue < int > Q;

void citire_graf()
{
    f >> n >> m >> start;
    for ( int i = 1; i <= n ; i++ ) f >> dist[i];
    for ( ; m-- ; )
    {
        f >> x >> y >> z;
        G[x].pb(mp(y,z));
        G[y].pb(mp(x,z));
    }
}

void resetare()
{
    for ( int i = 1; i <= n ; i++ ) d[i] = inf;
    memset(used,false,sizeof used);
}

void bellman_ford ( int i )
{
    d[i] = 0;
    used[i] = 1;
    Q.push(i);
    while ( !Q.empty() )
    {
        int nod = Q.front();
        Q.pop();
        used[nod] = 0;
        for ( vector < pair < int , int > > ::iterator j = G[nod].begin(); j != G[nod].end() ; j++ )
        {
            if ( d[ (*j).nod ] > d[nod] + (*j).cost )
            {
                d[ (*j).nod ] = d[nod] + (*j).cost;
                if ( !used [ (*j).nod ] )
                {
                    used [ (*j).nod ] = 1;
                    Q.push ( (*j).nod );
                }
            }
        }
    }
}

void solve()
{
    for ( int i = 1; i <= n ; i++ )
        if ( dist[i] != d[i] ){
            g << "NU" << "\n" ;
            return;
        }
    g << "DA" << "\n" ;
}

int main()
{
    f >> t;
    for ( ; t-- ; )
    {
        citire_graf();
        resetare();
        bellman_ford(start);
        solve();
        for ( int i = 1; i <= n ; i++ )
            G[i].erase(G[i].begin(),G[i].end());
    }
    return 0;
}