#include<fstream>
#include<iostream.h>
using namespace std;
#define inf 1<<20
#define NMAX 10000
int c[NMAX][NMAX];
int d[NMAX];
int n,k,m[NMAX],pred[NMAX],x0=1;
void afis();
void citire()
{
	ifstream f("dijkstra.in");
	f>>n>>k>>x0;
	int  i,j,x,y,cost;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			if(i!=j) c[i][j]=c[j][i]=inf;
	for(i=1;i<=k;i++)
		{
			f>>x>>y>>cost;
			c[x][y]=cost;
		}
	for(i=1;i<=n;i++)
	{
		d[i]=c[x0][i];pred[i]=x0;
	}
	m[x0]=1;pred[x0]=0;
	f.close();
}
void dijkstra ()
{
	int  i,j,poz;
	for(i=1;i<n;i++)
	{
		int  minim=inf,poz=-1;
		for(j=1;j<=n;j++)
			if(!m[j] && minim>d[j]) {minim=d[j];poz=j;}
		m[poz]=1;
		for(j=1;j<=n;j++)
			while(!m[j] && d[j]>d[poz]+c[poz][j])
			{
				d[j]=d[poz]+c[poz][j];
				pred[j]=poz;
			}
	}
}
void afis()
{
	int  i,j,drum[NMAX],lg;
	ofstream fout("dijkstra.out");
	for(i=1;i<=n;i++)
		if(i!=x0)
		{
			fout<<"costul drumului min de la "<<x0<<" la "<<i<<" este "<<d[i]<<"\n"<<"drum este : ";
			drum[0]=i;
			lg=0;
			while(pred[drum[lg]])
			{
				lg++;
				drum[lg]=pred[drum[lg-1]];
			}
			for(j=lg;j>=0;j--)
				fout<<' '<<drum[j];
			fout<<"\n";
		}
	fout.close();
}
int main ()
{
	citire();
	dijkstra();
	afis();
	return 0;
}