#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <string.h>

#define inf 1e9
#define nm 50002

using namespace std;

ifstream fin ("distante.in");
ofstream fout ("distante.out");

vector <pair <int, int> > G[nm];
int n , m , T;
int dist_min[nm] , dist_t_min[nm];
int nod_start;

priority_queue <int , vector<int> , comp> PQ;


class comp
{
public:
    bool operator () (const int &x, const int &y)
    {
        return dmin[x]>dmin[y];
    }
};


void dijkstra()
void read()
{
	fin >> T;	
	for(int i = 0 ; i < T ; i++)
	{
		fin >> n >> m >> nod_start;
		for (int j = 1 ; j <= n ; j++) fin >> dist_t_min[j];
		for (int j = 0 ; j < m ; j++)
		{
			fin >> x >> y >> c;
			G[x].push_back(make_pair(y , c));
			G[y].push_back(make_pair(x , c));
		}
		dijkstra();
	}
}

void dijkstra(){
	int varf_min;
	for(int i = 1 ; i <= n ; ++i)  dist_min[i] = inf;
	dist_min[nod_start] = 0;
	PQ.push(x0);
	while (q.size()){
		varf_min = PQ.top();
		PQ.pop();
		
		for(int i=0; i<G[vfmin].size(); ++i)
		{
			if(dmin[G[vfmin][i].first] > dmin[vfmin] + G[vfmin][i].second)
			{
				dmin[G[vfmin][i].first] = dmin[vfmin] + G[vfmin][i].second;
				q.push(G[vfmin][i].first);
			}
		}
		if(drumuri())
            g << "DA" << '\n';
        else
            g << "NU" << '\n';
 
        for(int j=0; j<=n; ++j)
        {
            G[j].clear();
        }
 
	}
	
}

int drumuri()
{
    for(int i=1; i<=n; ++i)
    {
        if(dist_min[i]!=dist_t_min[i])
            return 0;
    }
    return 1;
}

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