# include <fstream>
 # define dim 5000
 # define dim2 1009
 
 using namespace std;
 
 ifstream f ("distante.in");
 ofstream g ("distante.out");
 
 int a[dim][dim],costi[dim2],b[dim][dim],costf[dim2],uz[dim2],q[dim];
 int t,t1;
 int n,m,s;
 long suma;
 
 void rezolva(int s);
 void citire()
 {
	 int i;
	 int x,y,c;
	 f>>t;
	 t1 = t;
	 while ( t )
	 {
		 f>>n>>m>>s;
		 for( i = 1 ; i <= n;++ i)
			 f>>costi[i];
		 for( i = 1; i <=  m;++ i)
		 {
			 f>>x>>y>>c;
			 a[x][0]++;
			 a[x][a[x][0]] = y;
			 
			 b[x][y] = c;
			 
			 a[y][0]++;
			 a[y][a[y][0]] = x;
			 
			 b[y][x] = c;
			 
			 //rezolva(s);
		 }
		 t--;
	 }
	 
 }
 void afisare()
 {
	 int i,j;
	 for(i = 1;i <= n; i++)
	 {
		 for(j = 0;j <= n; j++)
			 g<<a[i][j]<<" ";
		 g<<"\n";
	 }
	 g<<"\n";
	 
	 for(i = 1;i <= n; i++)
	 {
		 for(j = 1;j <= n; j++)
			 g<<b[i][j]<<" ";
		 g<<"\n";
	 }
 }
 
 void afiseaza()
 {
	 int i;
	 for(i = 1;i <= t1;i ++)
	 {
		 g<<"DA";
		 g<<"\n";
	 }
 }
 /*void dfs(int x)
 {
	 int i;
	 //uz[x] = 1;
	 g<<x<<" "<<suma<<"\n";
	 for (i = 1; i <= a[x][0]; i++)
		 if(uz[a[x][i]] == 0)
		 {
			 uz[a[x][i]] = 1;
			 suma = suma + b[x][a[x][i]];
			 dfs(a[x][i]);
			 uz[a[x][i]] = 0;
			 suma = suma - b[x][a[x][i]];
			// g<<a[i][x]<<" ";
		 }
 }*/
 
 
 void rezolva()
 {
	 int st = 0,dr = 0,i,x,y,minim = 99999;
	 q[0] = s;
	 while(st <= dr)
	 {
		 x = q[st];
		 //suma = 0;
		 for( i = 1;i <= a[x][0]; i++ )
			 if(minim > b[x][a[x][i]])
			 {
				 minim = b[x][a[x][i]];
				 y = a[x][i];
				 //g<<suma<<"\n";
				 dr++;
				 q[dr] = a[x][y];
			 }
		st++;
	 }
 }
 
 int main()
 {
	 citire();
	// afisare();
	 rezolva();
	 afiseaza();
	 return 0;
 }