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

using namespace std;

ifstream f("distante.in");
ofstream g("distante.out");

const int maxn=50003;
const int INF=0x3f3f3f3f;

int t,n,dis[maxn],m,s,x,y,z,p,i,j,dism[maxn],k;

bool been[maxn];

queue<int>Q;

struct nod
{
    int w;
    int dis;
}
    one;

vector<nod>a[maxn];

int main()
{
    f>>t;
    for(p=1;p<=t;++p)
    {
        f>>n>>m>>s;
        for(i=1;i<=n;++i)
            f>>dis[i];
        for(i=1;i<=n;++i)
            while(a[i].size())
                a[i].pop_back();
        for(i=1;i<=m;++i)
        {
            f>>x>>y>>z;
            one.dis=z;
            one.w=y;
            a[x].push_back(one);
            one.w=x;
            a[y].push_back(one);
        }
        memset(dism,INF,sizeof(dism));
        memset(been,false,sizeof(been));
        Q.push(s);
        dism[s]=0;
        been[s]=true;
        while(!Q.empty())
        {
            k=Q.front();
            Q.pop();
            been[k]=false;
            for(vector<nod>::iterator it=a[k].begin();it!=a[k].end();++it)
                if(dism[k]+it->dis<dism[it->w])
                {
                    dism[it->w]=dism[k]+it->dis;
                    if(been[it->w]==false)
                        Q.push(it->w),been[it->w]=true;
                }
        }
            k=1;
            for(i=1;i<=n&&k;++i)
                if(dis[i]!=dism[i])
                    k=0;
            if(k)
                g<<"DA\n";
            else
                g<<"NU\n";

    }
    f.close();
    g.close();

    return 0;
}