#include <fstream>
#include <vector>
#define inf 999999999
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
vector<int> a[50001];
vector<int> c[50001];
bool vizitat[50001];
int dist[50001];
int heap[100001],sz,poz[50001];
int trb[50001];
int n,m,s,t;
void swaph(int i,int j)
{
    int aux=heap[i];
    heap[i]=heap[j];
    heap[j]=aux;
    aux=poz[heap[i]];
    poz[heap[i]]=poz[heap[j]];
    poz[heap[j]]=aux;
}
void up(int i)
{
    while(dist[heap[i]]<dist[heap[i/2]] and i>=2)
    {
        swaph(i,i/2);
        i/=2;
    }
}
void down(int i)
{
    while(2*i<=sz)
    {
        int minim=2*i;
        if(2*i<sz and dist[heap[2*i+1]]<dist[heap[minim]])
            minim++;
        if(dist[heap[minim]]<dist[heap[i]])
            swaph(minim,i);
        else return;
        i*=2;
    }
}
void add(int x)
{
    sz++;
    heap[sz]=x;
    poz[x]=sz;
    up(sz);
}
void pop()
{
    swaph(1,sz);
    poz[heap[sz]]=0;
    sz--;
    if(sz)
        down(1);
}
void dijkstra()
{
    dist[s]=0;
    sz=1;
    vizitat[s]=true;
    heap[1]=s;
    poz[s]=1;
    int k;
    while(sz)
    {
        k=heap[1];
        vizitat[k]=true;
        pop();
        int marime=a[k].size();
        for(int i=0;i<marime;i++)
            {
                if(dist[a[k][i]]>dist[k]+c[k][i])
                {
                    dist[a[k][i]]=dist[k]+c[k][i];
                    if(!vizitat[a[k][i]])
                    {
                        if(poz[a[k][i]])
                                up(poz[a[k][i]]);
                        else add(a[k][i]);
                    }
                }
            }
    }
}
void reset()
{
    for(int i=1;i<=n;i++)
    {
        a[i].clear();
        c[i].clear();
        poz[i]=0;
        vizitat[i]=false;
        dist[i]=inf;
        trb[i]=0;
    }
    sz=0;
}
void compara()
{
    for(int i=1;i<=n;i++)
        if(dist[i]!=trb[i])
        {
            g<<"NU\n";
            return;
        }
    g<<"DA\n";
}
int main()
{
    f>>t;
    for(int j=1;j<=t;j++)
    {
        f>>n>>m>>s;
        reset();
        for(int i=1;i<=n;i++)
            f>>trb[i];
        int a1,b1,c1;
        for(int i=1;i<=m;i++)
        {
            f>>a1>>b1>>c1;
            a[a1].push_back(b1);
            c[a1].push_back(c1);
            a[b1].push_back(a1);
            c[b1].push_back(c1);
        }
        dijkstra();
        compara();
    }
    return 0;
}