#define Dudica "Dudescu Alexandru"
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#define nmax 50005
#define inf 9999999999
using namespace std;
FILE *f1=fopen("distante.in","r"),*f2=fopen("distante.out","w");
vector <pair<int,int> > g[nmax];

int N,M,n,nrTeste,s;
int dmin[nmax],heap[nmax],pozHeap[nmax];
int d[nmax];

// Functii heap
void update(int x)
{
    while(x>=1&&dmin[heap[x]]<dmin[heap[(x-1)/2]])
    {
        swap(pozHeap[heap[x]],pozHeap[heap[(x-1)/2]]);
        swap(heap[x],heap[(x-1)/2]);
        x=(x-1)/2;
    }
}
int getMin()
{
    int minim,i=0,fiu;
    minim=heap[0];
    n--;
    pozHeap[heap[0]]=pozHeap[heap[n]];
    heap[0]=heap[n];
    do
    {
        fiu=0;
        if(2*i+1<n)
        {
            fiu=2*i+1;
            if(2*i+2<n&&dmin[heap[2*i+2]]<dmin[heap[2*i+1]])
            fiu++;
            if(dmin[heap[i]]<=dmin[heap[fiu]])fiu=0;
        }
        if(fiu)
        {
            swap(pozHeap[heap[i]],pozHeap[heap[fiu]]);
            swap(heap[i],heap[fiu]);
            i=fiu;
        }
    }while(fiu);
    return minim;
}
// Functii graf
void dijkstra()
{
    int vfMin,i,j;
    for(j=1;j<=N;j++)
    {
        vfMin=getMin();
        for(i=0;i<g[vfMin].size();i++)
            if(dmin[g[vfMin][i].first]>dmin[vfMin]+g[vfMin][i].second)
            {
                dmin[g[vfMin][i].first]=dmin[vfMin]+g[vfMin][i].second;
                update(pozHeap[g[vfMin][i].first]);
            }
    }
}
void eraseGraf()
{
    int i;
    for(i=1;i<=N;i++)
    {
        dmin[i]=inf;
        heap[i-1]=i;
        pozHeap[i]=i-1;
        while(g[i].size())g[i].pop_back();
    }
}
int main()
{
    fscanf(f1,"%d",&nrTeste);
    int test,i,x,y,c;
    //Pentru fiecare test
    for(test=1;test<=nrTeste;test++)
    {
        fscanf(f1,"%d %d %d",&N,&M,&s);

        for(i=1;i<=N;i++)
        fscanf(f1,"%d",&d[i]);

        eraseGraf();
        n=N;
        for(i=1;i<=M;i++)
        {
            fscanf(f1,"%d %d %d",&x,&y,&c);
            g[x].push_back(make_pair(y,c));
            g[y].push_back(make_pair(x,c));
            if(x==s)
            {
                dmin[y]=c;
                update(pozHeap[y]);
            }
            if(y==s)
            {
                dmin[x]=c;
                update(pozHeap[x]);
            }
        }
        dmin[s]=0;
        update(pozHeap[s]);

        dijkstra();

        bool ok=1;
        for(i=1;i<=N;i++)
        if(d[i]!=dmin[i]){ok=0;fprintf(f2,"NU\n");break;}
        if(ok)fprintf(f2,"DA\n");
    }
    fclose(f1);
    fclose(f2);
    return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.