#include<fstream>
#define infinit 10000;
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int c[20][20],n,i,j,k,s[20],ant[20],pas,min1,i0,d[20];
void citire()
{
	int i,j,k;
	f>>n>>i0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
				c[i][j]=0;
			else
				c[i][j]=10000;
			while(f>>i>>j>>k)
				c[i][j]=k;
}
void drum(int i)
{
	if(ant[i]!=0)
	{
		drum(ant[i]);
		g<<i<<" ";
	}
	else
		g<<i<<" ";
}
int main()
{
	citire();
	for(i=1;i<=n;i++)
	{
		s[i]=0;
		d[i]=c[i0][i];
		if(d[i]<10000)
			ant[i]=i0;
		else
			ant[i]=0;
	}
	s[i0]=1;
	ant[i0]=0;
	for(pas=1;pas<n;pas++)
	{
		min1=10000;
		for(i=1;i<=n;i++)
			if(!s[i]&&d[i]<min1)
			{
				min1=d[i];
				k=i;
			}
			s[k]=1;
			for(i=1;i<=n;i++)
				if(!s[i]&&d[i]>d[k]+c[k][i])
				{
					d[i]=d[k]+c[k][i];
					ant[i]=k;
				}
	}
	for(i=1;i<=n;i++)
	{
		g<<"drumul minim de la"<<" "<<" "<<i0<<" "<<"la"<<" "<<i<<" "<<"este"<<" "<<d[i]<<" ";
		g<<"trece prin"<<" "; 
		drum(i);
		g<<"\n";
	}
	return 0;
}