#include <fstream>
using namespace std;

#define DIM 100
#define INF 0x3f3f3f3f
int d[DIM];
int c[DIM][DIM];
bool v[DIM];
int t[DIM];
int n, S;

void Read();
void Dijkstra(int S);
void Write();
void Write(int );

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


int main()
{
	Read();
	Dijkstra(S);
	Write();
	Write(5);
	
	fin.close();
	fout.close();
	
	return 0;
	
}

void Read()
{
	fin >> n >> S;
	for ( int i = 1; i <= n; ++i )
		for ( int j = 1; j <= n; ++j )
			if ( i != j )
				c[i][j] = INF;
	int x, y, cost;
	while ( fin >> x >> y >> cost )
		c[x][y] = c[y][x] = cost;
	
}

void Dijkstra(int S)	// O(n*n)
{
	for ( int i = 1; i <= n; ++i )
	{
		d[i] = c[S][i];
		if ( d[i] < INF && i != S )
			t[i] = S;
	}
	
	int k, dmin;
	v[S] = true;
	d[S] = 0;  // se stie
	for ( int p = 1; p < n; ++p )	// n-1 pasi
	{
		dmin = INF;
		for ( int i = 1; i <= n; ++i )
			if ( !v[i] && d[i] < dmin )
			{
				k = i; 
				dmin = d[i];
			}
		v[k] = true;
		for ( int i = 1; i <= n; ++i )
			if ( !v[i] && d[i] > d[k] + c[k][i] )
			{
				d[i] = d[k] + c[k][i];
				t[i] = k;
			}
	}
	
}

void Write()
{
	for ( int i = 1; i <= n; ++i )
		fout << d[i] << ' ';
	fout << '\n';
}

void Write(int i)
{
	if ( i == 0 ) return;
	Write(t[i]);
	fout << i << ' ';
}