#include <fstream>
using namespace std;

int d[1<<16],v[1<<16],s[1<<16],place[1<<16],n,m;
const int inf=1<<30;
struct arc{int x,y,d;} a[1<<19];
bool use[1<<16];

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

bool cmp(arc a,arc b)
{
	return a.x<b.x;
}

inline void sch(int &a,int &b)
{
	int d=a;
	a=b;
	b=d;
	d=place[a];
	place[a]=place[b];
	place[b]=d;
}

inline void up(int x)
{
	if (x>1 && d[v[x]]<d[v[x>>1]])
	{
		sch(v[x],v[x>>1]);
		up(x>>1);
	}
}

inline void down(int x)
{
	int q=x;
	if (2*x<=v[0] && d[v[2*x]]<d[v[q]])
		q=2*x;
	if (2*x<v[0] && d[v[2*x+1]]<d[v[q]])
		q=2*x+1;
	if (q!=x)
	{
		sch(v[x],v[q]);
		down(q);
	}
}

void dijkstra(int start)
{
	int i,j,X;
	in>>n>>m;
	for (i=1;i<=m;i++)
		in>>a[i].x>>a[i].y>>a[i].d;
	sort(a+1,a+m+1,cmp);
	for (i=j=1;i<=n;i++)
	{
		for (;j<=m && a[j].x<i;j++);
		s[i]=j;
		d[i]=inf;
	}
	s[n+1]=m+1;
	v[++v[0]]=start;
	X=1000;
	d[start]=0;
	while (X)
	{
		X=v[1];
		use[X]=true;
		v[1]=v[v[0]--];
		down(1);
		for (i=s[X];i<s[X+1];i++)
		{
			if (!use[a[i].y])
			{
				use[a[i].y]=true;
				v[++v[0]]=a[i].y;
				place[a[i].y]=v[0];
			}
			if (d[a[i].y]>d[X]+a[i].d)
			{
				d[a[i].y]=d[X]+a[i].d;
				up(place[a[i].y]);
			}
		}
	}
}

int main()
{
	in>>t;
	while (t--)
	{
		in>>n>>m>>s;
		for (i=1;i<=n;i++)
			in>>
		dijkstra(s);