#include<cstdio>
#define N 50000
#define M 100000
#define oo 2000000000
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;
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;
	}
}
int minim()
{
	int min=oo,pmin=-1;
	for (int i=1; i<=n; ++i)
		if (!sel[i]&&d[i]<min)
		{
			min=d[i];
			pmin=i;
		}
	return pmin;
}
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;
	}
}
void dijkstra(int x)
{
	for (int i=1; i<=n; ++i)
	{
		d[i]=oo;
		sel[i]=false;
	}
	d[x]=0;
	for(int i=1; i<n; ++i)
	{
		x=minim();
		if (x==-1) return;
		sel[x]=true;
		update(x);
	}
}
inline bool verific()
{
	for(int i=1; i<=n; ++i)
		if (r[i]!=d[i])
			return false;
	return true;
}
void citire()
{
	freopen("distante.in","r",stdin);
	freopen("distante.out","w",stdout);
	short int t;
	scanf("%hd\n",&t);
	while (t)
	{
		fgets(s,99,stdin);
		parsare();
		for (int i=1; i<=n; ++i)
			scanf("%d\n",&r[i]);
		for (int i=1; i<=m; ++i)
		{
			fgets(s,99,stdin);
			parsare1(i);
			++d[v[i].x];
			++d[v[i].y];
		}
		bool ok=false;
		if (n>max){ ok=true;max=n;
		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;
		}
		}
		if (!ok)
			for (int i=1; i<=n; ++i){a[i][0]=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");
		--t;
	}	

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