#include<fstream>
#include<vector>
#include<cstring>
#include<queue>

#define nmax 50020
#define oo 10000000
using namespace std;

ifstream fin("distnate.in");
ofstream fout("distante.out");

bool s[nmax];//vizitarea nodurilor intermediare
int d[nmax], n, m  ;//distnta minima de la nodul r la nodul indice
int x,y,dis;
int l[nmax];
struct
Nod{
    int x, cost;
    Nod(int _x, int _cost)
    {
      x = _x;
      cost = _cost;
    }
    Nod()
    {
        x = 0; cost = 0;
    }
    bool operator < (const Nod &x) const{
        return cost > x.cost;
    }
} ;
vector <Nod> T[nmax]; //graful

void dijkstra(int r)
{
   int i , c, y ,x;
   for(int  i =1; i <= n; i++)
        d[i] = oo, s[i] = false;

    d[r] = 0;
    priority_queue <Nod> H;

    H.push(Nod(r,d[r]));

    while(!H.empty())
    {
        x = H.top().x;
        H.pop();
        if(s[x])
            continue;
        s[x] = true;
        for(vector <Nod> :: iterator it = T[x].begin(); it != T[x].end(); it++)
        {
            y = it -> x;
            c = it -> cost + d[x];
            if(c < d[y])
            {
                d[y] = c;
                H.push(Nod (y, d[y]) );
            }
        }
    }

    int ver = 0 ;
    for(int i = 1; i <= n;i++)
        if(d[i] == oo)
            d[i] = 0 ;
    for(int i = 1; i <= n;i++)
        if(d[i] != l[i] ){
            fout <<"NU" <<'\n'; ver = 1; break;
        }
    if(!ver)
    fout <<"DA" <<'\n';


}
void read()
{
    int nr ;
    fin >>nr;
    while(nr--)
    {
        int sursa;
        fin >> n >> m >> sursa;
        for(int i = 1; i <= n; i++)
            fin>>l[i],
            T[i].clear();
        for(int i = 1; i <= m ;i++)
        {
            fin >>x >> y >>dis;
            T[x].push_back(Nod(y,dis));

        }
        dijkstra(sursa);
    }



}
int main()
{
    read();

    fin.close();
    return 0;;

}