#include <fstream>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#define Max_Value 0x3f3f3f3f
#define Max_Nodes 50010
#define DIM 8192
using namespace std;
ifstream fin ("distante.in");
ofstream fout ("distante.out");
int T, N, M, S, My_Dist[Max_Nodes], His_Dist[Max_Nodes];
char P[DIM + 16], *now;
vector < pair < int, int > > V[Max_Nodes];
multiset < pair < int, int > > Heap;
string Sol;

void Read_Data();
void Dijkstra();
void Verifica_Corectitudinea();
int Get();
void Verif();

int main()
{
    now = P;
    Verif();
    T = Get();
    while (T--)
    {
        Read_Data();
        Dijkstra();
        Verifica_Corectitudinea();
        fout << Sol;
    }

    return 0;
}

void Read_Data()
{
    Verif();
    N = Get(); M = Get(); S = Get();
    for (int i = 1; i <= N; i++) {
        His_Dist[i] = Get();
        V[i].clear();
    }

    for (int i = 1, x, y, c; i <= M; i++) {
        x = Get(); y = Get(); c = Get();
        V[x].push_back( { y, c } );
        V[y].push_back( { x, c } );
    }
}

void Dijkstra()
{
    memset(My_Dist, Max_Value, sizeof(My_Dist));
    My_Dist[S] = 0;
    Heap.insert( { 0, S } );

    while (!Heap.empty())
    {
        pair < int, int > nod = *Heap.begin();
        Heap.erase(nod);

        for (vector < pair < int, int > > :: iterator it = V[nod.second].begin(); it != V[nod.second].end(); it++)
        {
            if (My_Dist[nod.second] + it->second < My_Dist[it->first])
            {
                Heap.erase( { My_Dist[it->first], it->first } );
                My_Dist[it->first] = My_Dist[nod.second] + it->second;
                Heap.insert( { My_Dist[it->first], it->first } );
            }
        }
    }
}

void Verifica_Corectitudinea()
{
    Sol = "DA\n";
    for (int i = 1; i <= N; i++) {
        if (My_Dist[i] != His_Dist[i]) {
            Sol = "NU\n";
            break;
        }
    }
}

inline void Verif()
{
    if (*now == '\0')
    {
        fin.get(P, DIM, '\0');
        now = P;
    }
}

inline int Get()
{
    while (*now < '0' || *now > '9') {
        now++;
        Verif();
    }

    int number = 0;
    while (*now >= '0' && *now <= '9') {
        number = number * 10 + *now - '0';
        now++;
        Verif();
    }
    return number;
}