#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits>
#define INF INT_MAX
using namespace std;
ifstream f ("distante.in");
ofstream g ("distante.out");
int t,n,m,s;
int distante_de_corectat[50001],distante_noi[50001];
bool viz[50001];
vector<pair<int,int>>adiacenta[50001];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
/// algoritmul Dijkstra
void citire()
{
    f>> n >> m >> s;
    for(int i = 1; i<=n; i++)
        f >> distante_de_corectat[i];
    for(int i = 1; i<=m; i++)
    {
        int a,b,c;
        f >> a >> b >> c;
        adiacenta[a].push_back({b,c});
        adiacenta[b].push_back({a,c});
    }
    for(int i = 1; i<=50000; i++)
    {
        distante_noi[i] = INF;
        viz[i] = 0;
    }
}
int main()
{
    f >> t;
    for(int i = 1; i<=t; i++)
    {
        citire();
        q.push({0,s});
        distante_noi[s] = 0;
        while(!q.empty())
        {
            int vf_curent = q.top().second;
            int cost_vf_curent = q.top().first;

            q.pop();

            if(!viz[vf_curent])
            {
                viz[vf_curent] = 1;
                for(int j = 0; j<adiacenta[vf_curent].size(); j++)
                {
                    int cost = adiacenta[vf_curent][j].second;
                    int nod = adiacenta[vf_curent][j].first;

                    if(distante_noi[nod] > distante_noi[vf_curent] + cost)
                    {
                        distante_noi[nod] = distante_noi[vf_curent] + cost;
                        q.push({cost,nod});
                    }
                }
            }
        }
        bool ok = 1;
        for(int j = 1; j<=n; j++)
        {
            if(distante_noi[j]!=distante_de_corectat[j])
            {
                ok = 0;
                break;
            }
        }
        if(ok)
            g << "DA";
        else
            g << "NU";
        g << endl;
    }
}