#include <set>
#include <vector>
#include <fstream>
#include <limits.h>

#define INF LONG_MAX

using namespace std;

struct graph{
    vector<pair<long int,long int> >* adj;
    long int sz;

    graph(const long int& n)
    {
        adj = new vector<pair<long int,long int> >[n];
        sz = n;
    }

    ~graph()
    {
        delete[] adj;
    }

    void insertEdge(const long int& u, const long int& v, const long int& w)
    {
        adj[u].push_back(make_pair(w,v));
        adj[v].push_back(make_pair(w,u));
    }

    long int size() const
    {
        return sz;
    }
};

bool dijkstra(const graph& gr, long int src, int* compare)
{
    set<pair<long int,long int> > vset;
    vector<long int> dist(gr.size(), INF);

    vset.insert(make_pair(0,src));
    dist[src] = 0;

    while(!vset.empty())
    {
        pair<long int, long int> t = *vset.begin();
        vset.erase(vset.begin());

        long int vert = t.second;
        for(unsigned long int i = 0; i < gr.adj[vert].size(); i++)
        {
            long int u = gr.adj[vert][i].second;
            long int w = gr.adj[vert][i].first;


            if(dist[u] > dist[vert] + w)
            {
                if(dist[u] != INF)
                    vset.erase(vset.find(make_pair(dist[u], u)));
                dist[u] = dist[vert] + w;
                vset.insert(make_pair(dist[u], u));
            }
        }
    }
    for(long int i = 0; i < gr.size(); i++)
        if(dist[i] != compare[i])
            return false;
    return true;
}

int t;
int n, m, s;
int v[50000];
graph* gr;

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

    f >> t;
    for(int tt = 0; tt < t; tt++)
    {
        f >> n >> m >> s;
        gr = new graph(n);

        for(long int i = 0; i < n; i++)
            f >> v[i];
        for(long int i = 0; i < m; i++)
        {
            long int a, b, c;
            f >> a >> b >> c;
            a--;b--;
            (*gr).insertEdge(a,b,c);
        }

        g << ((dijkstra(*gr,0,v))?"DA":"NU") << '\n';
        //delete gr;
    }

    return 0;
}