#include <cstdio>
#include <set>
#include <vector>
#define DMAX 50005
#define INF 2000000000

using namespace std;

struct muchie
{
int vf,cost;
};

vector <muchie> G[DMAX];
set <pair<int,int> > Q;

FILE*fin=fopen("distante.in","r");
FILE*fout=fopen("distante.out","w");

int n,m,vfs;
int CZ[DMAX],CF[DMAX];

void citire();
void init();
void dijkstra();
void afisare(int caz);

int main()
{
int T,i;
fscanf(fin,"%d",&T);
for (i=1;i<=T;i++)
    {
    citire();
    init();
    dijkstra();
    }
    return 0;
}

void citire()
{
int i,x,y,cost;
muchie aux;
fscanf(fin,"%d %d %d",&n,&m,&vfs);
for (i=1;i<=n;i++) fscanf(fin,"%d",&CZ[i]);
for (i=1;i<=m;i++)
    {
     fscanf(fin,"%d %d %d",&x,&y,&cost);
     aux.vf=y; aux.cost=cost;
     G[x].push_back(aux);
    }
}

void init()
{
int i;
for (i=1;i<=n;i++) CF[i]=INF;
CF[vfs]=0;
Q.insert( make_pair(0,vfs) );
}

void dijkstra()
{
int vf,minim;
int i;
while(Q.size()>0)
     {
      minim=(*Q.begin()).first;
      vf=(*Q.begin()).second;
      Q.erase(*Q.begin());
      for (i=0;i<G[vf].size();i++)
           if (CF[ G[vf][i].vf ]>G[vf][i].cost+minim)
              {
               CF[ G[vf][i].vf ]=G[vf][i].cost+minim;
               Q.insert( make_pair(CF[ G[vf][i].vf ],G[vf][i].vf) );
              }
     }
for (i=1;i<=n;i++)
     if (CZ[i]!=CF[i])
        {
         afisare(0);
         return;
        }
afisare(1);
}

void afisare(int caz)
{
if (caz==1) fprintf(fout,"DA\n");
    else fprintf(fout,"NU\n");
}