#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
long long distante[50010], d[50010];
#define int long long
int  n, m, start;
struct my_struct {
    int nod, cost;
}t, nod_current;
vector<my_struct> v[250022];
queue<int>_q;
int viz[100001];
void marcare(int n)
{
    int k = 10000101;
    for (int i = 1; i <= n; i++)
    {
        d[i] = k;
    }
}
void read(int& N, int& M, int& start)
{
    f >> N >> M >> start;
    for (int i = 1; i <= N; i++)
    {
        f >> distante[i];
        viz[i] = 0;
        v[i].clear();
    }
    int a, b, c;
    for (int i = 1; i <= m; i++)
    {
        f >> a >> t.nod >> t.cost;
        v[a].push_back(t);
    }

}
void  bellman_ford(int a)
{
    _q.push(a);
    viz[a] = 1;
    d[a] = 0;
    int nod_din_coada = 0;
    while (!_q.empty())
    {
        nod_din_coada = _q.front();
        viz[nod_din_coada] = 0;
        //de fiecare data cand trecem prin aceset nod-->nod_din_coada crestem un contor pt el si daca am trecut de m
        // cand e cost negativ, revine prin nod_din_coada
        _q.pop();
        for (int i = 0; i < v[nod_din_coada].size(); i++)
        {
            nod_current = v[nod_din_coada][i];
            if (d[nod_din_coada] + nod_current.cost < d[nod_current.nod])
            {
                d[nod_current.nod] = d[nod_din_coada] + nod_current.cost;
                if (!viz[nod_current.nod])
                {
                    _q.push(nod_current.nod);
                    viz[nod_current.nod] = 1;
                }
            }
        }
    }
}
int is_in(int nods_number)
{
    for (int i = 1; i <= nods_number; i++)
    {
        if (d[i] != distante[i])return 0;
    }
    return 1;
}
void solve(int n)
{
    if (is_in(n))
    {
        g << "DA" << '\n';
    }
    else
        g << "NU" << '\n';
}
int main() {
    int nr_grafs = 0;
    f >> nr_grafs;
    for (int i = 1; i <= nr_grafs; i++)
    {
        read(n, m, start);
        marcare(n);

        bellman_ford(start);
        solve(start);
    }

}