#include <iostream>
#include<string>
#include<vector>
#include<fstream>
#include<list>
#include<set>
using namespace std;


void dfs_asmax(int nr_noduri, vector<int>&v, vector<vector<int>>&lista, vector<bool>& vizit, int& nod) {

	vizit[nod] = 1;

	for (int i = 0; i < lista[nod].size(); i++) {

		if (vizit[lista[nod][i]] == false) {

			dfs_asmax(nr_noduri, v, lista, vizit, lista[nod][i]);

			if (v[lista[nod][i]] > 0) {

				v[nod] += v[lista[nod][i]];
			}
		}
	}
}
void asmax() {

	fstream f("asmax.in");
	int n;//nr noduri
	f >> n;

	vector<int>v(n + 1, 0);//valorile nodurilor
	for (int i = 1; i <= n; i++) {

		f >> v[i];
	}

	int x, y;
	vector<vector<int>>lista;//lista de muchii
	lista.resize(n + 1);
	while (f >> x >> y) {

		lista[x].push_back(y);
		lista[y].push_back(x);
	}

	f.close();

	vector<bool> vizit(n + 1, 0);//vector de vizite

	int maxi = -1001;//suma noului subarbore

	dfs_asmax(n, v, lista, vizit, n);


	for (int i = 1; i <= n; i++) {

		if (v[i] > maxi) {

			maxi = v[i];
		}
	}

	ofstream g("asmax.out");
	g << maxi;
	g.close();
}

void dijkstra(int nr_noduri, int nr_muchii, vector<vector<pair<int, int>>>& lista, int infinit, vector<int>& dist) {

	set<pair<int, int>>set;
	dist[1] = 0;
	set.insert(make_pair(0, 1));

	while (!set.empty()) {

		int init = set.begin()->second;
		set.erase(set.begin());

		for (int i = 0; i < lista[init].size(); i++) {

			int final = lista[init][i].first;
			int cost = lista[init][i].second;

			if (dist[final] > dist[init] + cost) {

				if (dist[final] != infinit) {

					set.erase(set.find(make_pair(dist[final], final)));
				}

				dist[final] = dist[init] + cost;
				set.insert(make_pair(dist[final], final));
			}
		}
	}
}
void citire_dijkstra() {
	int infinit = std::numeric_limits<int>::max();
	
	ifstream f("distante.in");
	int nr_grafuri;
	f >> nr_grafuri;

	for (int i = 1; i <= nr_grafuri; i++) {

		int nr_noduri, nr_muchii, sursa;
		f >> nr_noduri >> nr_muchii >> sursa;

		vector<int>v(nr_noduri + 1, 0);
		for (int j = 1; j <= nr_noduri; j++) {

			f >> v[j];
		}
		vector<vector<pair<int,int>>>lista;
		lista.resize(nr_noduri + 1);

		for (int j = 1; j <= nr_muchii; j++) {

			int c, x, y;
			f >> x >> y >> c;
			lista[x].push_back(make_pair(y, c));
			lista[y].push_back(make_pair(x, c));
		}
		vector<int>dist(nr_noduri, 0);
		dijkstra(nr_noduri, nr_muchii, lista, infinit, dist);

		bool ok = true;
		ofstream g("distante.out");
		for (int j = 1; j <= nr_noduri; j++) {

			if (dist[j] != v[j]) {
				g << "NU" << endl;
				ok = false;
				break;
			}
		}
		if (ok == true) {

			g << "DA" << endl;
		}
	}
	f.close();
	//g.close();
}




int main()
{
	citire_dijkstra();
}