#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

const int MAXN = 50005;
const int INF = 1000000;

int N, M,start;
vector< pair<int, int> > G[MAXN];//tin minte muchiiile si costul (practic vecinii si costurile -un fel de lista de vecini)
int Dmin[MAXN],D_zaharel[MAXN];//Distanta minima pana la un nod

	ifstream fin("distante.in");

	ofstream fout("distante.out");

void citeste() {
int i;


	fin >> N >> M>>start;
	  for(i=1;i<=N;i++) {fin>>D_zaharel[i];
  G[i].clear();	                   }

    for ( i = 0; i < M; ++i) {
		int a, b, c;


		fin >> a >> b >> c;
		G[a].push_back(make_pair(b, c));//vecinul lui a este b iar costul arcului (a,b) este c
		G[b].push_back(make_pair(a,c));
	}
}

void dijkstra() {
	bool viz[MAXN];// tipul bool (prescurtarea de la boolean poate lua valoarea true sau false
				// este deci mai convenabil(din punct de vedere al memoriei folosite) sa folosim bool in de int(4 octeti)

	queue<int> Q;  //queue =coada
	int i;
	while (!Q.empty()) Q.pop();

for(i=0;i<=MAXN;i++)
{
                    Dmin[i]=INF;
                    viz[i]=false;
                    }



	Dmin[start] = 0;
	Q.push(start);// Q.push(x) adauga pe x in coada(strcutura de tip FIFO)
	viz[start] = true;

	while (!Q.empty()) {  //cat timp coada nu s-a golit
		int nod = Q.front(); //retinem in nod primul element din coada (care asteapta sa fie servit)
		Q.pop();           //eliminam primul element din  coada
		viz[nod] = false;
//vector< pair<int, int> >::iterator it   -NU VA SPERIATI
// it este un iterator folosit pentru a parcurge itemii din vector
// este la fel ca si o variabila numai ca ii spunem ca va parcurge valori de tipul vector< pair<int, int> >

		//reamintim ca in G[nod][] retinem vecinii lui nod impreuna cu costurile aferente distantei de la nod la vecin
		//it = G[nod].begin() iteratorul cu numele it va retine inceputul listei de vecini a nodului nod
		// G[nod].end() =capatul listei de vecini a lui nod
		for (vector< pair<int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
			if (Dmin[nod] + it->second < Dmin[it->first]) {
				Dmin[it->first] = Dmin[nod] + it->second;
				if (!viz[it->first]) {
					Q.push(it->first);
					viz[it->first] = true;
				}
			}
	}
}

void afisare() {
int i;
	for (i = 1; i <= N; ++i)
		if (Dmin[i]!=D_zaharel[i]) {fout<<"NU\n";break;}
 if (i>N) fout<<"DA\n";
}

int main() {
    int nr_grafuri,i;
    fin>>nr_grafuri;
    for(i=1;i<=nr_grafuri;i++)
    {
	citeste();
	dijkstra();
	afisare();}
	fin.close();
	fout.close();
}