#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("distante.in");
ofstream out("distante.out");
const int inf = (1 << 30);
const int maxn = 50005;
pair <int, int> H[maxn];
vector <pair <int, int> > v[maxn];
int pozitii[maxn];
int verif[maxn];
int dist[maxn];
int lg = 0;
void reinit()
{
    lg = 0;
    for(int i = 0; i < maxn; i++)
    {
        v[i].clear();
        dist[i] = inf;
        H[i] = make_pair(inf, inf);
        pozitii[i] = 0;
    }
}

void up(int F)
{
    if(F / 2 >= 1 && H[F].first < H[F / 2].first)
    {
        swap(H[F], H[F / 2]);
        pozitii[H[F].second] = F;
        pozitii[H[F / 2].second] = F / 2;
        up(F / 2);
    }
}

void down(int F)
{
    int S = F * 2;
    if(S < lg && H[S].first > H[S + 1].first)
        S++;
    if(S <= lg && H[S].first < H[F].first)
    {
        swap(H[S], H[F]);
        pozitii[H[F].second] = F;
        pozitii[H[S].second] = S;
        down(S);
    }
}

void _erase_(int pos)
{
    swap(pozitii[H[pos].second], pozitii[H[lg].second]);
    swap(H[pos], H[lg]);
    lg--;
    up(pos);
    down(pos);
}

void inserare(int x, int p)
{
    lg++;
    H[lg] = make_pair(x, p);
    pozitii[p] = lg;
    up(lg);
}

void dijkstra()
{
    while(lg > 0)
    {
        pair <int, int> elmn = H[1];
        _erase_(1);
        for(auto it : v[elmn.second])
        {
            if(dist[it.first] > dist[elmn.second] + it.second)
            {
                dist[it.first] = dist[elmn.second] + it.second;
                H[pozitii[it.first]].first = dist[it.first];
                up(pozitii[it.first]);
                down(pozitii[it.first]);
            }
        }
    }
}

int pas()
{
    int n, m, s;
    in >> n >> m >> s;
    reinit();
    for(int i = 1; i <= n; i++)
        in >> verif[i];
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;
        v[x].push_back(make_pair(y, cost));
        v[y].push_back(make_pair(x, cost));
    }
    dist[s] = 0;
    inserare(0, 1);
    for(int i = 2; i <= n; i++)
        inserare(inf, i);
    dijkstra();
    //for(int i = 1; i <= n; i++)
    //    cerr << dist[i] << " ";
    for(int i = 1; i <= n; i++)
        if(dist[i] != verif[i])
            return 0;
    return 1;
}
int main()
{
    int T;
    in >> T;
    for(int i = 1; i <= T; i++)
    {
        if(pas() == 0)
            out << "NU";
        else
            out << "DA";
        out << "\n";
    }
    return 0;
}