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

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

const int inf = 1000000005;
int task;

bool dijkstra()
{
    int n, m, source, x, y, node, nnode, c;

    vector < int > dist, vis, sol;
    vector < vector < int > > graph, cost;
    priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > s;

    in >> n >> m >> source;

    sol.push_back(0);

    for(int i = 1; i <= n; ++i)
    {
        in >> x;
        sol.push_back(x);
    }

    graph.resize(n + 1);
    cost.resize(n + 1);
    dist.resize(n + 1, inf);
    vis.resize(n + 1, 0);

    for(int i = 1; i <= m; ++i)
    {
        in >> x >> y >> c;

        graph[x].push_back(y);
        cost[x].push_back(c);
        graph[y].push_back(x);
        cost[y].push_back(c);
    }

    dist[source] = 0;
    s.push({0, source});

    while(!s.empty())
    {
        node = s.top().second;
        c = s.top().first;
        s.pop();

        if(vis[node] == 1) continue;
        else vis[node] = 1;

        for(int i = 0; i < graph[node].size(); ++i)
        {
            nnode = graph[node][i];

            if(dist[nnode] > cost[node][i] + c)
            {
                dist[nnode] = cost[node][i] + c;
                if(dist[nnode] < sol[nnode])
                    return 0;
                s.push({dist[nnode], nnode});
            }
        }
    }

    for(int i = 1; i <= n; ++i)
        if(sol[i] != dist[i])
            return 0;

    return 1;
}

void solve()
{
    bool ok;

    in >> task;

    for(int i = 1; i <= task; ++i)
    {
        ok = dijkstra();
        if(ok == 1) out << "DA" << "\n";
        else out << "NU" << "\n";
    }
}

int main()
{
    solve();
    return 0;
}