#include <bits/stdc++.h>
#define NN 50005
#define INF 1000000005
using namespace std;
ifstream fin ("distante.in");
ofstream fout ("distante.out");

int teste, n, m, p, d[NN], vis[NN], verif[NN], a, b, c;
int vfmin, dmin, vf, dis;
pair<int, int> aux;
vector <pair<int, int> > v[NN];
set <pair<int, int> > s;

void test()
{
    fin >> n >> m >> p;
    for(int i = 1 ; i <= n ; i++)
    {
        d[i] = INF;
        vis[i] = 0;
        fin >> verif[i];
        if(verif[i] == -1)
            verif[i] = INF;
    }
    for(int i = 1 ; i <= m ; i++)
    {
        fin >> a >> b >> c;
        v[a].push_back({b, c});
    }
    d[p] = 0;
    s.insert({d[p], p});
    while(!s.empty())
    {
        aux = *s.begin();
        s.erase(aux);
        vfmin = aux.second;
        dmin = aux.first;
        vis[vfmin] = 1;
        for(int i = 0 ; i < v[vfmin].size() ; i++)
        {
            aux = v[vfmin][i];
            vf = aux.first;
            dis = aux.second;
            if(vis[vf] == 0 && d[vf] > dmin + dis)
            {
                s.erase({d[vf], vf});
                d[vf] = dmin + dis;
                s.insert({d[vf], vf});
            }
        }
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(d[i] != verif[i])
        {
            fout << "NU" << '\n';
            return;
        }
    }
    fout << "DA" << '\n';
}

int main()
{
    fin >> teste;
    for(int i = 1 ; i <= teste ; i++)
        test();
    return 0;
}