#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define n1 first
#define c1 second

using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
const int inf = 0x3f3f3f3f;
queue <int > q;
vector < pair <int, int> >v[50000];
int t,sol[50000],sol1[50000],n,m,k,a,b,c;
bool ok;

void bfs(int s)
{
    q.push(s);
    for(int i=1; i<=n; i++)
    sol[i]=inf;
    sol[s]=0;
    while(!q.empty())
    {
        int curent=q.front();
        q.pop();
        for(int i=0; i<v[curent].size(); i++)
            if(sol[v[curent][i].n1]>sol[curent]+v[curent][i].c1)
            {
                q.push(v[curent][i].n1);
                sol[v[curent][i].n1]=sol[curent]+v[curent][i].c1;
            }
            }

}
int main()
{
    f>>t;
    for(int i=1; i<=t; i++)
    {
        f>>n>>m>>k;
        for(int j=1; j<=n; j++)
        {
            f>>sol1[j];
            v[j].clear();
        }
        ok=true;
        for(int j=1; j<=m; j++)
        {
            f>>a>>b>>c;
            v[a].push_back(make_pair(b,c));
            v[b].push_back(make_pair(a,c));
            if(sol1[a]>sol1[b]+c||sol1[b]>sol1[a]+c&&ok==true){g<<"NU\n";ok=false;}
        }
        if(ok==false)break;
        if(sol1[k]!=0){g<<"NU\n";break;}else
        {
        bfs(k);
        for(int j=1; j<=n; j++)
        if(sol1[j]!=sol[j]){ok=false;break;}
        if(ok==false)g<<"NU\n";
                else g<<"DA\n";
        }
    }

    return 0;
}