#include <fstream>
#include <vector>
#include <queue>
#define INF 2000000000

using namespace std;

int n, m, s;
int dtest[50010], d[50010];
struct NOD
{
	int x, cost;
};
vector <NOD> a[50010];
bool v[50010];

inline void BellmanFord(int s)
{
    queue <int> Q;
	Q.push(s);
	d[s] = 0;
	v[s] = true;
	int x, y, cost;
	NOD aux;

	vector <NOD>::iterator it, final;

	while(!Q.empty())
	{
		x = Q.front();
		Q.pop();
		it = a[x].begin();
		final = a[x].end();
		for (; it!=final; it++)
		{
			aux = *it;
			y = aux.x;
			cost = aux.cost;
			if (d[y] > d[x] + cost)
			{
				d[y] = d[x] + cost;
				if (v[y] == false)
				{
					Q.push(y);
					v[y] = true;
				}
			}
		}
		v[x] = false;
	}
}

inline bool Verificare()
{
	int i;
	for (i=1; i<=n; i++)
		if (d[i] !=dtest[i])
			return false;
	return true;
}

inline void SolveNeoptim()
{
	ifstream f("distante.in");
	ofstream g("distante.out");
	int T, i;
	f>>T;
	int x, y, cost;
	NOD aux;
	bool rez;
	while(T--)
	{
		f>>n>>m>>s;
		for(i=1; i<=n; i++)
		{
			d[i] = INF;
			f>>dtest[i];
		}
		d[s] = 0;
		for (i=1; i<=m; i++)
		{
			f>>x>>y>>cost;
			aux.x = y;
			aux.cost = cost;
			a[x].push_back(aux);
			aux.x = x;
			a[y].push_back(aux);
		}

		BellmanFord(s);
		rez = Verificare();
		if (rez==true)
			g<<"DA\n";
		else
			g<<"NU\n";
		// trebuie sa mai distrug vectorii

		for (i=1; i<=n; i++)
			a[i].clear();
	}
	f.close();
	g.close();
}

inline bool VerificareBuna()
{
    int i;
    for (i=1; i<=n; i++)
        if (!v[i])
            return false;
    return true;
}

inline void SolveBun()
{
    ifstream f("distante.in");
    ofstream g("distante.out");
    int t;
    bool rez;
    f>>t;
    int i, x, y, cost;
    while (t--)
    {
        f>>n>>m>>s;
        for (i = 1; i<=n; i++)
        {
            v[i] = false;
            f>>d[i];
        }
        v[s] = true;
        for (i = 1; i<=m; i++)
        {
            f>>x>>y>>cost;
            if (d[x] + cost == d[y])
                v[y] = true;
            if (d[y] + cost == d[x])
                v[x] = true;
        }
        rez = VerificareBuna();
        if (rez==true)
            g<<"DA\n";
        else
            g<<"NU\n";
    }
    f.close();
    g.close();
}

int main()
{
	//SolveNeoptim();
	SolveBun();
	return 0;
}