#include <cstdlib>

template<class T>
class Node{
	T info;
	Node* next;
public:
	Node(T _info, Node* _next = NULL) { info = _info; next = _next; }
	Node(Node& _n) { info = _n.info; next = _n.next; }
	Node* getNext() { return next; }
	T getInfo()		{ return info; }
	void setNext(Node* _n) { next = _n; }
	void setInfo(T _info)  { inof = _info; }
	~Node() {}
};

template<class T>
class Comparator{

public:
	virtual int compare(T a, T b)
	{
		if (a < b) return -1;
		if (a > b) return 1;
		return 0;
	}
};

template<class T>
class PriorityQueue{
	Node<T> *q;
	int length;
	Comparator<T> cmp;
	Node<T>* getHead() { return q; }
public:
	PriorityQueue() : q(NULL), length(0) { }
	PriorityQueue(Node<T>* _n) : q(_n), length(1) { }
	PriorityQueue(PriorityQueue& _q);
	void push(T);
	T pop();
	T top();
	int size();
	bool isEmpty();
	~PriorityQueue();
};

template <class T>
PriorityQueue<T>::PriorityQueue(PriorityQueue& _q)
{
	q = new Node<T>(_q.top());
	Node<T> *ant, *p;
	ant = q;

	for (p = _q.getHead()->getNext(); p != NULL; p = p->getNext())
	{
		Node<T> *aux = new Node<T>(*p);
		ant->setNext(aux);
		ant = aux;
	}
}

template <class T>
void PriorityQueue<T>::push(T e)
{
	Node<T> *n = new Node<T>(e);
	Node<T> *p;
	length++;
	
	if (q == NULL) 
	{
		q = n;
		return;
	}

	if (cmp.compare(n->getInfo(), q->getInfo()) < 0)
	{
		n->setNext(q);
		q = n;
		return;
	}

	for (p = q; p->getNext() != NULL; p = p->getNext())
		if (cmp.compare(n->getInfo(), p->getNext()->getInfo()) < 0)
		{
			n->setNext(p->getNext());
			p->setNext(n);
			return;
		}
	p->setNext(n);	
}

template <class T>
T PriorityQueue<T>::pop()
{
	T c;
	Node<T> *aux = NULL;

	if (q == NULL) return NULL;

	aux = q;
	q = q->getNext();
	c = aux->getInfo();
	delete aux;
	aux = NULL;
	length--;

	return c;
}

template <class T>
T PriorityQueue<T>::top()
{
	return q->getInfo();
}

template <class T>
int PriorityQueue<T>::size()
{
	return length;
}

template <class T>
bool isEmpty()
{
	return (length == 0);
}

template <class T>
PriorityQueue<T>::~PriorityQueue()
{
	Node<T> *p = NULL, *aux = NULL;
	for (p = q; p != NULL; p = p->getNext())
	{
		if (aux == NULL)
			aux = p;
		else
		{
			delete aux;
			aux = NULL;
		}
	}
	if (aux != NULL) delete aux;
}

#include <iostream>
#include <vector>
#include <fstream>

#define MAX 10000
#define INF 0x3f3f3f

using namespace std;

int n, m, d[MAX], dc[MAX];
vector< pair <int, int> > g[MAX];
ofstream fout("distante.out");

template<>
class Comparator<int>{
public:
	int compare(int a, int b)
	{
		if (d[a] < d[b]) return -1;
		if (d[a] > d[b]) return 1;
		return 0;
	}
};
PriorityQueue<int> q;

void Dijkstra(int s)
{
	int i, min;

	for (i = 1; i <= n; i++)
		d[i] = INF;
	d[s] = 0;
	q.push(s);
	
	while (q.size() != 0)
	{
		min = q.pop();

		for (vector< pair<int, int> >::iterator it = g[min].begin(); it != g[min].end(); ++it)
			if (d[min] + it->second < d[it->first])
			{
				d[it->first] = d[min] + it->second;
				q.push(it->first);
			}
	}
}

void Read()
{
	int a, b, c, t, s, i;
	ifstream fin("distante.in");
	fin >> t;

	for (; t; --t)
	{
		fin >> n >> m >> s;
		
		for (i = 1; i <= n; i++)
			fin >> dc[i];

		for (i = 0; i < m; i++)
		{
			fin >> a >> b >> c;
			g[a].push_back(make_pair(b, c));
		}

		Dijkstra(s);
	}
	fin.close();
}

void Write()
{
	
	for (int i = 1; i <= n; i++)
		if (d[i] != dc[i]) {fout << "NU\n"; return; }
	fout << "DA\n";
}

int main()
{
	
	Read();
	fout.close();

	system("pause");
	return 0;
}