#include <bits/stdc++.h>
#define NMAX 50005
#define inf 1<<30
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
int n,m,t,sursa,d[NMAX],dist[NMAX],heap[NMAX],pos[NMAX];
struct dijkstraa
{
    int nod,cost;
    dijkstraa *next;
}*a[NMAX],*q;
void add(int nod1,int nod2,int cost)
{
    dijkstraa *q=new dijkstraa;
    q->cost=cost;
    q->nod=nod2;
    q->next=a[nod1];
    a[nod1]=q;
}
void read()
{
    int x,y,D;
    f>>n>>m>>sursa;
    for(int i=1; i<=n; i++)f>>d[i];
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>D;
        add(x,y,D);
        add(y,x,D);
    }
}
void schimb(int x,int y){swap(pos[heap[x]],pos[heap[y]]); swap(heap[x],heap[y]);}
void heapup(int i)
{
    if(dist[heap[i/2]]<dist[heap[i]]||i==1)return;
    schimb(i,i/2);
    heapup(i/2);
}
void heapdown(int i)
{
    if(i*2>m)return;
    int st=dist[heap[2*i]],dr;
    if(i*2+1<=m)dr=dist[heap[2*i+1]]; else dr=st+1;
    if(min(st,dr)<dist[heap[i]])
        if(st<dr)
        {
            schimb(i,2*i);
            heapdown(2*i);
        }
        else
        {
            schimb(i,2*i+1);
            heapdown(2*i+1);
        }
}
void dijkstra()
{
    for(int i=2; i<=n; i++)dist[i]=inf,pos[i]=-1;
    m=1; heap[1]=1; dist[1]=0; pos[1]=1;
    while(m)
    {
        int MIN=heap[1];
        schimb(1,m);
        --m; heapdown(1);
        q=a[MIN];
        while(q)
        {
            if(dist[q->nod]>dist[MIN]+q->cost)
            {
                dist[q->nod]=dist[MIN]+q->cost;
                if(pos[q->nod]!=-1)
                    heapup(pos[q->nod]);
                else
                {
                    heap[++m]=q->nod;
                    pos[heap[m]]=m;
                    heapup(m);
                }
            }
            q=q->next;
        }
    }
}
void solve()
{
    f>>t;
    for(int k=1; k<=t; k++)
    {
        read();
        dijkstra();
        int ok=0;
        for(int i=1; i<=n; i++)
            if(dist[i]!=d[i])
            {
                g<<"NU\n";
                ok=1;
                break;
            }
        if(ok==0)
            g<<"DA\n";
    }
}
int main()
{
    solve();
    return 0;
}