#include<cstdio>
#define N 50000
#define M 100000
#define oo 2000000000
#define F 2500001
char s[100];
bool sel[N];
struct distante{int x,y,z;}v[M];
int d[M], r[N],*a[N],*a1[N],n,m,s1,max,h[M],nh;
void parsare()
{
	int nr=0;
	short int num=0;
	for (int i=0; s[i]&&s[i]!=10;++i)
	{
		while (s[i]&&s[i]!=10&&s[i]>='0'&&s[i]<='9')
		{
			nr=nr*10+s[i]-'0';
			++i;
		}
		++num;
		if (num==1)
			n=nr;
		else
			if (num==2)
				m=nr;
			else
				s1=nr;
		nr=0;
	}
}
void parsare1(int k)
{
	int nr=0;
	short int num=0;
	for (int i=0; s[i]&&s[i]!=10;++i)
	{
		while (s[i]&&s[i]!=10&&s[i]>='0'&&s[i]<='9')
		{
			nr=nr*10+s[i]-'0';
			++i;
		}
		++num;
		if (num==1)
			v[k].x=nr;
		else
			if (num==2)
				v[k].y=nr;
			else
				v[k].z=nr;
		nr=0;
	}
}
inline bool verific()
{
	for(int i=1; i<=n; ++i)
		if (r[i]!=d[i])
			return false;
	return true;
}
inline void schimb(int &x,int &y)   
{   
    int aux=x;   
    x=y;   
    y=aux;   
}   
  
void coboara(int p)   
{   
    int pmin=p;   
    if(2*p<=nh && d[h[2*p]] < d[h[pmin]])   
        pmin=2*p;   
    if(2*p+1<=nh && d[h[2*p+1]] < d[h[pmin]])   
        pmin=2*p+1;   
    if(pmin!=p)   
    {   
        schimb(h[p],h[pmin]);   
        coboara(pmin);   
    }   
}   
  
void urca(int p)   
{   
    while(p>=2 && d[h[p/2]] > d[h[p]])   
    {   
        schimb(h[p],h[p/2]);   
        p/=2;   
    }   
}   
  
int minim()   
{   
    while(nh && sel[h[1]])   
    {   
        schimb(h[1],h[nh--]);   
        if(!sel[h[1]])   
            coboara(1);   
    }   
    if(nh==0)   
        return -1;   
    return h[1];   
}   
void update(int x)   
{   
    for (int i=1; i<=a[x][0]; ++i)   
    {   
        int y=a[x][i],c=a1[x][i];   
        if (d[x]+c<d[y])   
        {   
            d[y]=d[x]+c;   
            h[++nh]=y;   
            urca(nh);   
        }   
    }   
}   
void dijkstra(int x0)   
{   
    for (int i=1; i<=n; ++i)   
    {   
        d[i]=oo;   
        sel[i]=false;   
    }   
    d[x0]=0;   
    h[++nh]=x0;   
    for (int i=1; i<n; ++i)   
    {   
        int x=minim();   
        if(x==-1)   
            return;   
        sel[x]=true;   
        update(x);   
    }   
}   
void refac()
{
	for (int i=1; i<=n; ++i)
	{
		delete a[i];
		delete a1[i];
		d[i]=0;
	}
}
void citire()
{
	freopen("distante.in","r",stdin);
	freopen("distante.out","w",stdout);
	short int t;
	scanf("%hd\n",&t);
	while (t)
	{
		fgets(s,F,stdin);
		parsare();
		for (int i=1; i<=n; ++i)
			scanf("%d\n",&r[i]);
		for (int i=1; i<=m; ++i)
		{
			fgets(s,F,stdin);
			parsare1(i);
			++d[v[i].x];
			++d[v[i].y];
		}
		for (int i=1; i<=n; ++i)
		{
			a[i]=new int [1+d[i]];
			a[i][0]=0;
			a1[i]=new int [1+d[i]];
			a1[i][0]=0;
		}
	       
		for (int i=1; i<=m; ++i)
		{
			a[v[i].x][++a[v[i].x][0]]=v[i].y;
			a[v[i].y][++a[v[i].y][0]]=v[i].x;
			a1[v[i].x][++a1[v[i].x][0]]=v[i].z;
			a1[v[i].y][++a1[v[i].y][0]]=v[i].z;
		}
		dijkstra(s1);
		if (verific())
			printf("DA\n");
		else
			printf("NU\n");
		refac();
		--t;
	}	

}
int main()
{
	citire();
	return 0;
}