#include <fstream>

using namespace std ;

ifstream f ("11b.in") ;
ofstream g ("11b.out") ;

int n , vp , a[105][105] , x[105] , nr , vizitat[105] , sol[105] , cost_minim = 9999 ;

void afis ( int c )
{
if ( c < cost_minim )
{
cost_minim = c ;
for ( int i = 1 ; i <= n ; ++i )
sol[i] = x[i] ;
sol[n+1] = vp ;
}
}

void ham ( int i , int c )
{
if ( i == n + 1 && a[x[n]][vp] )
afis ( c + a[x[n]][vp]) ;
else if ( i <= n )
for ( int j = 1 ; j <= n ; ++j )
if ( a[x[i-1]][j] && vizitat[j] == 0 )
{
x[i] = j ;
vizitat[j] = 1 ;
ham ( i + 1 , c + a[x[i-1]][j] ) ;
vizitat[j] = 0 ;
}
}

int main ()
{
f >> n >> vp ;
int i , j , c;
while ( f >> i >> j >> c )
a[i][j] = a[j][i] = c ;
x[1] = vp ;
vizitat[vp] = 1 ;
ham ( 2 , 0 ) ;
g << cost_minim << "\n" ;
for ( int i = 1 ; i <= n + 1 ; ++i )
g << sol[i] << " " ;
return 0 ;
}