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

using namespace std;
const int NMAX = 50001;
#define fi first
#define se second

int n, m, sursa, d[NMAX], dist[NMAX];
vector<pair<int, int>> G[NMAX];
bitset<NMAX> viz;

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

void citire()
{
    int x, y, c;
    f >> n >> m >> sursa;
    for(int i = 1; i <= n; i++)
        f >> d[i], G[i].clear();
    //
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }
}

void dijkstra(int nod)
{
    viz.reset();
    fill(dist + 1, dist + n + 1, 1e9);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > Q;
    //
    dist[nod] = 0;
    Q.push({0, nod});
    //
    while(!Q.empty())
    {
        auto crt = Q.top();
        Q.pop();
        //
        if(viz[crt.se])
            continue;
        viz[crt.se] = 1;
        //
        for(const auto &next : G[crt.se])
        {
            if(dist[crt.se] + next.se < dist[next.fi])
            {
                dist[next.fi] = dist[crt.se] + next.se;
                Q.push({dist[next.fi], next.fi});
            }
        }
    }
}

int main()
{
    int T;
    f >> T;
    while(T--)
    {
        citire();
        dijkstra(sursa);
        bool ok = 1;
        for(int i = 1; i <= n; i++)
            if(d[i] != dist[i])
            {
                g << "NU\n";
                ok = 0;
                break;
            }
        if(ok) g << "DA\n";
    }
    f.close();
    g.close();
    return 0;
}